Tight Security Bounds for Key-Alternating Ciphers

Abstract

A $t$-round key-alternating cipher (also called 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$: {$0,1$}$^n$$\rightarrow${$0,1$}$^n$ and a key $k=k_0||\ldots||k_t\in${$0,1$}$^{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^{tn/(t+1)}$ 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^{2n/3}$ for $t\geq 2$, Steinberger (2012) proved security of $2^{3n/4}$ for $t\geq 3$, and Lampe, Patarin and Seurin (2012) proved security of $2^{tn/(t+2)}$ for all even values of $t$, thus “barely” falling short of the desired $2^{tn/(t+1)}$.

Our contribution in this work is to prove the long-sought-for security bound of $2^{tn/(t+1)}$, up to a constant multiplicative factor depending on $t$. Our method is essentially an application of Patarin’s H-coefficient technique.