Paper 2012/035

Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations

Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Francois-Xavier Standaert, John Steinberger, and Elmar Tischhauser


This paper considers---for the first time---the concept of key-alternating ciphers in a provable security setting. Key-alternating 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 Even-Mansour 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 non-black box manner. However, we conjecture its security is $2^{128}$.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. extended abstract to appear at Eurocrypt 2012, this is the full version
Block ciphersprovable securityEven-Mansour constructionAES
Contact author(s)
g leander @ mat dtu dk
2012-01-30: revised
2012-01-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrey Bogdanov and Lars R.  Knudsen and Gregor Leander and Francois-Xavier Standaert and John Steinberger and Elmar Tischhauser},
      title = {Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2012/035},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.