2024/12/06 by Chen Bai, Bai, Chen, Atul Mantri +2
Computer Science · #Quantum Computing Algorithms and Architecture #Cryptographic Implementations and Security #Chaos-based Image/Signal Encryption
paper · pdf · doi:10.48550/arxiv.2412.05026
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)2 + 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.