Paper 2013/061
On the Indifferentiability of Key-Alternating Ciphers
Elena Andreeva, Andrey Bogdanov, Yevgeniy Dodis, Bart Mennink, and John P. Steinberger
Abstract
The Advanced Encryption Standard (AES) is the most widely used block cipher. The high level structure of AES can be viewed as a (10-round) key-alternating cipher, where a t-round key-alternating cipher KA_t consists of a small number $t$ of fixed permutations P_i on n bits, separated by key addition: KA_t(K,m)= k_t + P_t(... k_2 + P_2(k_1 + P_1(k_0 + m))...), where (k_0,...,k_t) are obtained from the master key K using some key derivation function. For t=1, KA_1 collapses to the well-known Even-Mansour cipher, which is known to be indistinguishable from a (secret) random permutation, if P_1 is modeled as a (public) random permutation. In this work we seek for stronger security of key-alternating ciphers --- indifferentiability from an ideal cipher --- and ask the question under which conditions on the key derivation function and for how many rounds t is the key-alternating cipher KA_t indifferentiable from the ideal cipher, assuming P_1,...,P_t are (public) random permutations? As our main result, we give an affirmative answer for t=5, showing that the 5-round key-alternating cipher KA_5 is indifferentiable from an ideal cipher, assuming P_1,...,P_5 are five independent random permutations, and the key derivation function sets all rounds keys k_i=f(K), where 0<= i<= 5 and f is modeled as a random oracle. Moreover, when |K|=|m|, we show we can set f(K)=P_0(K)+K, giving an n-bit block cipher with an n-bit key, making only six calls to n-bit permutations P_0,P_1,P_2,P_3,P_4,P_5.
Metadata
- Available format(s)
-
PDF PS
- Category
- Foundations
- Publication info
- Published elsewhere. An extended abstract will appear at CRYPTO 2013
- Keywords
- Even-Mansourideal cipherkey alternating cipherindifferentiability
- Contact author(s)
-
elena andreeva @ esat kuleuven be
a bogdanov @ mat dtu dk
dodis @ cs nyu edu
bart mennink @ esat kuleuven be
jpsteinb @ gmail com - History
- 2013-06-07: last of 3 revisions
- 2013-02-06: received
- See all versions
- Short URL
- https://ia.cr/2013/061
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/061, author = {Elena Andreeva and Andrey Bogdanov and Yevgeniy Dodis and Bart Mennink and John P. Steinberger}, title = {On the Indifferentiability of Key-Alternating Ciphers}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/061}, year = {2013}, url = {https://eprint.iacr.org/2013/061} }