Abstract
We study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even--Mansour construction. KAC abstracts the round structure of practical block ciphers as public permutations interleaved with key XORs. The 1-round KAC or EM setting already highlights the power of quantum superposition access: EM is secure against classical and Q1 adversaries (quantum access to the public permutation), but insecure in the Q2 model. The security of multi-round KACs remain largely unexplored; in particular, whether the quantum-classical separation extends beyond a single round had remained open. 1) Quantum Lower Bounds. We prove security of the t-round KAC against a non-adaptive adversary in both the Q1 and Q2 models. In the Q1 model, any distinguiser requires Ω(2^tn/2t+1) oracle queries to distinguish the cipher from a random permutation, whereas classically any distinguisher needs Ω(2^tn/t+1) queries. As a corollary, we obtain a Q2 lower bound of Ω (2^(t-1)n/2t) quantum queries. Thus, for t ≥ 2, the exponential Q1-Q2 gap collapses in the non-adaptive setting, partially resolving an open problem posed by Kuwakado and Morii (2012). Our proofs develop a controlled-reprogramming framework within a quantum hybrid argument, sidestepping the lack of quantum recording techniques for permutation-based ciphers; we expect this framework to be useful for analyzing other post-quantum symmetric primitives. 2) Quantum Key-Recovery Attack. We give the first non-trivial quantum key-recovery algorithm for t-round KAC in the Q1 model. It makes O(2^α n) queries with α = t(t+1)/(t+1)² + 1, improving on the best known classical bound of O(2^α' n) with α' = t/t+1. The algorithm adapts quantum walk techniques to the KAC structure.