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)^2 + 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.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)^2 + 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.

arXiv:2412.05026Dec 6, 20240 citations

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)^2 + 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.