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) pseudo-randomness 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 O(2~(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 {direct+} P_2 (k_1 {direct+} P_1 (k_0 {direct+}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 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 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.