Paper 2014/443

Minimizing the Two-Round Even-Mansour Cipher

Shan Chen, Rodolphe Lampe, Jooyoung Lee, Yannick Seurin, and John P. Steinberger

Abstract

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,\dots ,P_r$ as follows: given a sequence of $n$-bit round keys $k_0,\dots ,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,\dots ,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 $$ and the permutations $$ are independent}. In particular, for two rounds, the current state of knowledge is that the block cipher $$ is provably secure up to $$ queries of the adversary, when $$, $$, and $$ are three independent $$-bit keys, and $$ and $$ are two independent random $$-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 $$-bit key and one $$-bit permutation}. Our answer is positive: when the three $$-bit round keys $$, $$, and $$ are adequately derived from an $$-bit master key $$, and the same permutation $$ is used in place of $$ and $$, we prove a qualitatively similar $$ 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.

Note: An abridged version appears in the proceedings of CRYPTO 2014. This is the full version. The revised version of Dec. 18, 2014 contains some additional results and a more extensive discussion of the security bounds.