Minimizing the Two-Round Even–Mansour Cipher

Abstract

The $r$-round (iterated) Even–Mansour cipher (also known as key-alternating cipher) defines a block cipher from $r$ fixed public $n$-bit permutations $P_1,\ldots,P_r$ as follows: Given a sequence of $n$-bit round keys $k_0,\ldots,k_r$, an $n$-bit plaintext $x$ is encrypted by xoring round key $k_0$, applying permutation $P_1$, xoring round key $k_1$, etc. The (strong) pseudorandomness of this construction in the random permutation model (i.e., when the permutations $P_1,\ldots,P_r$ are public random permutation oracles that the adversary can query in a black-box way) was studied in a number of recent papers, culminating with the work of Chen and Steinberger (EUROCRYPT 2014), who proved that the r-round Even–Mansour cipher is indistinguishable from a truly random permutation up to $\mathcal{O}(2^{\frac{r}{r+1}n})$ queries of any adaptive adversary (which is an optimal security bound since it matches a simple distinguishing attack). All results in this entire line of work share the common restriction that they only hold under the assumption that the round keys $k_0,\ldots,k_r$ and the permutations $P_1,\ldots,P_r$ are independent. In particular, for two rounds, the current state of knowledge is that the block cipher $E(x)=k_2\oplus P_2(k_1\oplus P_1(k_0\oplus x))$ is provably secure up to $\mathcal{O}(2^{2n/3})$ queries of the adversary, when $k_0$, $k_1$, and $k_2$ are three independent $n$-bit keys, and $P_1$ and $P_2$ are two independent random $n$-bit permutations. In this paper, we ask whether one can obtain a similar bound for the two-round Even–Mansour cipher from just one $n$-bit key and one $n$-bit permutation. Our answer is positive: When the three $n$-bit round keys $k_0$, $k_1$, and $k_2$ are adequately derived from an $n$-bit master key $k$, and the same permutation $P$ is used in place of $P_1$ and $P_2$, we prove a qualitatively similar $\tilde{\mathcal{O}}(2^{2n/3})$ security bound (in the random permutation model). To the best of our knowledge, this is the first “beyond the birthday bound” security result for AES-like ciphers that does not assume independent round keys.