Minimizing the Two-Round Even-Mansour Cipher

The r-round (iterated) Even-Mansour cipher (also known as key-alternating cipher) defines a block cipher from r fixed public n-bit permutations P1,...,Pr as follows Given a sequence of n-bit round keys k0,...,kr, an n-bit plaintext x is encrypted by xoring round key k0, applying permutation P1, xoring round key k1, etc. The (strong) pseudorandomness of this construction in the random permutation model (i.e., when the permutations P1,...,Pr 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 (EUROCRYPT2014), who proved that the r-round Even-Mansour cipher is indistinguishable from a truly random permutation up to O(2+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 the round keys k0,...,kr and the permutations P1,...,Pr are independent. In particular, for two rounds, the current state of knowledge is that the block cipher E(x)=k2 circle plus P2(k1 circle plus P1(k0 circle plus x)) is provably secure up to O(22n/3) queries of the adversary, when k0, k1, and k2 are three independent n-bit keys, and P1 and P2 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 onen-bit key and onen-bit permutation. Our answer is positive When the three n-bit round keys k0, k1, and k2 are adequately derived from an n-bit master key k, and the same permutation P is used in place of P1 and P2, we prove a qualitatively similar O 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