Paper 2013/061
On the Indifferentiability of KeyAlternating 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 (10round) keyalternating cipher, where a tround keyalternating 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 wellknown EvenMansour 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 keyalternating 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 keyalternating 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 5round keyalternating 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 nbit block cipher with an nbit key, making only six calls to nbit 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
 EvenMansourideal 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
 20130607: last of 3 revisions
 20130206: 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 KeyAlternating Ciphers}, howpublished = {Cryptology ePrint Archive, Paper 2013/061}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/061}}, url = {https://eprint.iacr.org/2013/061} }