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

P

1

,…,

P

r

as follows: given a sequence of

n

-bit round keys

k

0

,…,

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

,…,

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{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

the round keys k

0

,…,

k

r

and the permutations P

1

,…,

P

r

are independent

. In particular, for two rounds, the current state of knowledge is that the block cipher

E

(

x

) = 

k

2

 ⊕ 

P

2

(

k

1

 ⊕ 

P

1

(

k

0

 ⊕ 

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

$ \widetilde{ \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.