Paper 2013/222
Tight security bounds for keyalternating ciphers
Shan Chen and John Steinberger
Abstract
A $t$round \emph{keyalternating cipher} (also called \emph{iterated EvenMansour cipher}) can be viewed as an abstraction of AES. It defines a cipher $E$ from $t$ fixed public permutations $P_1, \ldots, P_t : \bits^n \ra \bits^n$ and a key $k = k_0\Vert \cdots \Vert k_t \in \bits^{n(t+1)}$ by setting $E_{k}(x) = k_t \oplus P_t(k_{t1} \oplus P_{t1}(\cdots k_1 \oplus P_1(k_0 \oplus x) \cdots))$. The indistinguishability of $E_k$ from a truly random permutation by an adversary who also has oracle access to the (public) random permutations $P_1, \ldots, P_t$ was investigated in 1997 by Even and Mansour for $t = 1$ and for higher values of $t$ in a series of recent papers. For $t = 1$, Even and Mansour proved indistinguishability security up to $2^{n/2}$ queries, which is tight. Much later Bogdanov et al$.$ (2011) conjectured that security should be $2^{\frac{t}{t+1}n}$ queries for general $t$, which matches an easy distinguishing attack (so security cannot be more) . A number of partial results have been obtained supporting this conjecture, besides Even and Mansour's original result for $t = 1$: Bogdanov et al$.$ proved security of $2^{\frac{2}{3}n}$ for $t \geq 2$, Steinberger (2012) proved security of $2^{\frac{3}{4}n}$ for $t \geq 3$, and Lampe, Patarin and Seurin (2012) proved security of $2^{\frac{t}{t+2}n}$ for all even values of $t$, thus "barely" falling short of the desired $2^{\frac{t}{t+1}n}$. Our contribution in this work is to prove the longsoughtfor security bound of $2^{\frac{t}{t+1}n}$, up to a constant multiplicative factor depending on $t$. Our method is essentially an application of Patarin's Hcoefficient technique. The proof contains some couplinglike and inclusionexclusion ideas, but the main trick that pushes the computations through is to stick with the combinatorics and to refrain from rounding any quantities too early. For the reader's interest, we include a selfcontained tutorial on the Hcoefficient technique.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2014
 Contact author(s)
 jpsteinb @ gmail com
 History
 20140207: last of 2 revisions
 20130429: received
 See all versions
 Short URL
 https://ia.cr/2013/222
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/222, author = {Shan Chen and John Steinberger}, title = {Tight security bounds for keyalternating ciphers}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/222}, year = {2013}, url = {https://eprint.iacr.org/2013/222} }