International Association
for Cryptologic Research

The $r$-round (iterated) \\emph{Even-Mansour cipher} (also known as \\emph{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 $O(2^{\\frac{rn}{r+1}})$ 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 \\emph{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 $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 \\emph{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{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.