Paper 2026/930

Improved Quantum Attacks on Iterated Even-Mansour Ciphers with Classical Queries

Abstract

The Even-Mansour cipher is a construction of a keyed pseudorandom permutation from a random unkeyed permutation. Its generalization to multiple rounds, known as iterated Even-Mansour or key-alternating cipher, is an important abstraction in block cipher design. Yet, while the security of single-round Even-Mansour is tight in the quantum setting (with attacks matching security proofs), much less is known on multi-round versions. In this paper we study the quantum security of iterated Even-Mansour ciphers with two keys (the key-schedule alternates between two independent keys), which model concrete block ciphers like LED. We give the first quantum attacks improving asymptotically over exhaustive key search for 4 to 6 rounds. On 4 rounds, we present three attacks: two using collision search and one using a quantum version of the multibridge attack of Dinur, Dunkelman, Keller and Shamir (ASIACRYPT 2014), which relies on a quantum walk. The latter reaches up to a quantum time $2^{7n/9}$ where $n$ is the block size, compared to $2^n$ of exhaustive key search. On 6 rounds, we present an attack of quantum time $2^{n} / \sqrt{\log n}$, adapting classical attacks based on multicollisions. In both cases, our new attacks require only classical known-plaintext queries.