Abstract
We describe highly efficient constructions, XE and XEX, that turn a blockcipher \(E: \mathcal{K} \times \{0, 1 \}^{n} \rightarrow \{0, 1 \}^{n}\) into a tweakable blockcipher \({E}: \mathcal{K} \times \mathcal{T} \times \{0, 1 \}^{n} \rightarrow \{0, 1 \}^{n}\) having tweak space \(\mathcal{T} = \{0, 1 \}^{n} \times \mathbb{I}\) where \(\mathbb{I}\) is a set of tuples of integers such as \(\mathbb{I} = [..2^{n/2}] \times [0..10]\). When tweak T is obtained from tweak S by incrementing one if its numerical components, the cost to compute \({E}^{T}_{K}(M)\) having already computed some \({E}^{S}_{K}(M')\) is one blockcipher call plus a small and constant number of elementary machine operations. Our constructions work by associating to the i th coordinate of \(\mathbb{I}\) an element \(\alpha_{i} \epsilon \mathbb{F}^{*}_{2}n\) and multiplying by α i when one increments that component of the tweak. We illustrate the use of this approach by refining the authenticated-encryption scheme OCB and the message authentication code PMAC, yielding variants of these algorithms that are simpler and faster than the original schemes, and yet have simpler proofs. Our results bolster the thesis of Liskov, Rivest, and Wagner [10] that a desirable approach for designing modes of operation is to start from a tweakable blockcipher. We elaborate on their idea, suggesting the kind of tweak space, usage-discipline, and blockcipher-based instantiations that give rise to simple and efficient modes.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption: Analysis of the DES modes of operation. In: Symposium on Foundations of Computer Science, FOCS 1997, pp. 394–403. IEEE Computer Society, Los Alamitos (1997)
Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining message authentication code. Journal of Computer and System Sciences 61(3) (December 2000); Earlier version in CRYPTO 1994
Bellare, M., Rogaway, P., Wagner, D.: The EAX Mode of operation. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 389–407. Springer, Heidelberg (2004)
Black, J., Rogaway, P.: A block-cipher mode of operation for parallelizable message authentication. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 384–397. Springer, Heidelberg (2002)
Gligor, V., Donescu, P.: Fast encryption and authentication: XCBC encryption and XECB authentication modes. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 92–108. Springer, Heidelberg (2002)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28, 270–299 (1984)
Halevi, S., Rogaway, P.: A parallelizable enciphering mode. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 292–304. Springer, Heidelberg (2004)
Kilian, J., Rogaway, P.: How to protect DES against exhaustive key search (an analysis of DESX). J. of Cryptology 14(1), 17–35 (2001)
Jutla, C.: Encryption modes with almost free message integrity. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 529–544. Springer, Heidelberg (2001)
Liskov, M., Rivest, R., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 31–46. Springer, Heidelberg (2002)
Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory 24, 106–110 (1978)
Pollard, J.: Monte Carlo methods for index computation (mod p). Mathematics of Computation 32, 918–924 (1978)
Rogaway, P.: Authenticated-encryption with associated-data. In: ACM Conference on Computer and Communications Security 2002, CCS 2002, pp. 98–107. ACM Press, New York (2002)
Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC (manuscript 2004); Full version of this paper, available from the author’s web page
Rogaway, P., Bellare, M., Black, J.: OCB: A block-cipher mode of operation for efficient authenticated encryption. ACM Transactions on Information and System Security 6(3), 365–403 (2003); Earlier version, with T. Krovetz, in CCS 2001
Schroeppel, R.: The hasty pudding cipher. AES candidate submitted to NIST (1998)
Whiting, D., Housley, R., Ferguson, N.: Counter with CBC-MAC (CCM). Network Working Group RFC 3610. The Internet Society (September 2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rogaway, P. (2004). Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC. In: Lee, P.J. (eds) Advances in Cryptology - ASIACRYPT 2004. ASIACRYPT 2004. Lecture Notes in Computer Science, vol 3329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30539-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-30539-2_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23975-8
Online ISBN: 978-3-540-30539-2
eBook Packages: Springer Book Archive