Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks

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^{frac{tn}{2t+1}}\) oracle queries to distinguish the cipher from a random permutation, whereas classically any distinguisher needs Ω\(2^{frac{tn}{t+1}}\) queries. As a corollary, we obtain a Q2 lower bound of Ω\(2^{frac{(t-1\)n}{2t}}) quantum queries. Thus, for t geq 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 α= frac{t(t+1)}{(t+1)² + 1}, improving on the best known classical bound of O\(2^{α' n}\) with α' = frac{t}{t+1}. The algorithm adapts quantum walk techniques to the KAC structure.