An Asymptotically Tight Security Analysis of the Iterated Even-Mansour Cipher
AbstractWe analyze the security of the iterated Even-Mansour cipher (a.k.a. key-alternating cipher), a very simple and natural construction of a blockcipher in the random permutation model. This construction, first considered by Even and Mansour (J. Cryptology, 1997) with a single permutation, was recently generalized to use t permutations in the work of Bogdanov et al. (EUROCRYPT 2012). They proved that the construction is secure up to \( \mathcal{O} (N^{2/3})\) queries (where N is the domain size of the permutations), as soon as the number t of rounds is 2 or more. This is tight for t = 2, however in the general case the best known attack requires Ω(N t/(t + 1)) queries. In this paper, we give asymptotically tight security proofs for two types of adversaries: 1 for non-adaptive chosen-plaintext adversaries, we prove that the construction achieves an optimal security bound of \( \mathcal{O} (N^{t/(t+1)})\) queries; 2 for adaptive chosen-plaintext and ciphertext adversaries, we prove that the construction achieves security up to \( \mathcal{O} (N^{t/(t+2)})\) queries (for t even). This improves previous results for t ≥ 6. Our proof crucially relies on the use of a coupling to upper-bound the statistical distance of the outputs of the iterated Even-Mansour cipher to the uniform distribution.KeywordsblockcipherEven-Mansour cipherkey-alternating cipherrandom permutation modelcouplingprovable security