Chosen-Key Secure Even-Mansour Cipher from a Single Permutation

Abstract

At EUROCRYPT 2015, Cogliati and Seurin proved that the 4-round Iterated Even-Mansour (IEM) cipher with Independent random Permutations and no key schedule EMIP₄(k, u) = k⊕p₄ ( k⊕p₃ ( k⊕p₂ (k⊕p₁ (k⊕u)))) is sequentially indifferentiable from an ideal cipher, which implies chosen-key security in the sense of correlation intractability. In practice, however, blockciphers such as the AES typically employ the same permutation at each round. To bridge the gap, we prove that the 4-round IEM cipher EMSP[φ]^p₄ (k, u) = k₄⊕p (k₃⊕p (k₂⊕p(k₁⊕p(k₀⊕u)))), whose round keys k_i = φⁱ(k) are derived using an affine permutation φ : {0, 1}ⁿ → {0, 1}ⁿ with certain properties, is sequentially indifferentiable from an ideal cipher. The function φ can be a linear orthomorphism, or φ(k) := k≫_a for some fixed integer a using cyclic shift. To our knowledge, this is the first indifferentiability-type result for blockciphers using identical round functions.