Paper 2012/035
KeyAlternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations
Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, FrancoisXavier Standaert, John Steinberger, and Elmar Tischhauser
Abstract
This paper considersfor the first timethe concept of keyalternating ciphers in a provable security setting. Keyalternating ciphers can be seen as a generalization of a construction proposed by Even and Mansour in 1991. This construction builds a block cipher $PX$ from an $n$bit permutation $P$ and two $n$bit keys $k_0$ and $k_1$, setting $PX_{k_0,k_1}(x)=k_1\oplus P(x\oplus k_0)$. Here we consider a (natural) extension of the EvenMansour construction with $t$ permutations $P_1,\ldots,P_t$ and $t+1$ keys, $k_0,\ldots, k_t$. We demonstrate in a formal model that such a cipher is secure in the sense that an attacker needs to make at least $2^{2n/3}$ queries to the underlying permutations to be able to distinguish the construction from random. We argue further that the bound is tight for $t=2$ but there is a gap in the bounds for $t>2$, which is left as an open and interesting problem. Additionally, in terms of statistical attacks, we show that the distribution of Fourier coefficients for the cipher over all keys is close to ideal. Lastly, we define a practical instance of the construction with $t=2$ using AES referred to as AES$^2$. Any attack on AES$^2$ with complexity below $2^{85}$ will have to make use of AES with a fixed known key in a nonblack box manner. However, we conjecture its security is $2^{128}$.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. extended abstract to appear at Eurocrypt 2012, this is the full version
 Keywords
 Block ciphersprovable securityEvenMansour constructionAES
 Contact author(s)
 g leander @ mat dtu dk
 History
 20120130: revised
 20120129: received
 See all versions
 Short URL
 https://ia.cr/2012/035
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/035, author = {Andrey Bogdanov and Lars R. Knudsen and Gregor Leander and FrancoisXavier Standaert and John Steinberger and Elmar Tischhauser}, title = {KeyAlternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations}, howpublished = {Cryptology ePrint Archive, Paper 2012/035}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/035}}, url = {https://eprint.iacr.org/2012/035} }