**Tight security bounds for key-alternating ciphers**

*Shan Chen, John Steinberger*

**Abstract: **A $t$-round \emph{key-alternating cipher} (also called \emph{iterated
Even-Mansour 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_{t-1}
\oplus P_{t-1}(\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 long-sought-for 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 H-coefficient technique. The proof contains some coupling-like and inclusion-exclusion 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 self-contained tutorial on the H-coefficient technique.

**Category / Keywords: **secret-key cryptography /

**Publication Info: **(none)

**Date: **received 15 Apr 2013, last revised 24 Sep 2013

**Contact author: **jpsteinb at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20130925:042756 (All versions of this report)

**Short URL: **ia.cr/2013/222

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]