Substitution-Permutation Networks (SPNs) constitute a major design paradigm for block ciphers. While the provable security of generic SPNs has been studied in the classical setting, their security against quantum adversaries remains largely unexplored. In this work, we provide the first provable security result for a generic SPN construction against quantum adversaries. Specifically, we prove that the generic 3-round linear SPN whose classical security was established by Dodis et al., instantiated with independent and uniformly distributed round and whitening keys, achieves post-quantum SPRP security in the Q1 model. In this model, construction queries are classical, while the adversary is given quantum forward and inverse access to the underlying public random permutation. The construction operates on a w n -bit state and applies this n -bit permutation, which corresponds to the S-box, in parallel to w state blocks in each round, with linear transformations and key additions between the S-box layers. For a constant w , our bound implies security up to approximately 2 n / 3 quantum and classical queries. Our proof builds on the hybrid argument introduced by Alagic et al. at EUROCRYPT 2022. The main technical challenge is to bound bad events caused by collisions among hidden internal values arising from the parallel and repeated use of the same public permutation. To overcome this difficulty, we develop new technical tools for bounding such internal-collision events in the presence of quantum forward and inverse access to the public random permutation. Our result also shows that the 3-round linear SPN can be viewed as a post-quantum-secure domain-extension method for constructing a keyed pseudorandom permutation on w n bits from a random permutation on n bits.
Substitution-Permutation Networks (SPNs) constitute a major design paradigm for block ciphers. While the provable security of generic SPNs has been studied in the classical setting, their security against quantum adversaries remains largely unexplored. In this work, we provide the first provable security result for a generic SPN construction against quantum adversaries. Specifically, we prove that the generic 3-round linear SPN whose classical security was established by Dodis et al., instantiated with independent and uniformly distributed round and whitening keys, achieves post-quantum SPRP security in the Q1 model. In this model, construction queries are classical, while the adversary is given quantum forward and inverse access to the underlying public random permutation. The construction operates on a w n -bit state and applies this n -bit permutation, which corresponds to the S-box, in parallel to w state blocks in each round, with linear transformations and key additions between the S-box layers. For a constant w , our bound implies security up to approximately 2 n / 3 quantum and classical queries. Our proof builds on the hybrid argument introduced by Alagic et al. at EUROCRYPT 2022. The main technical challenge is to bound bad events caused by collisions among hidden internal values arising from the parallel and repeated use of the same public permutation. To overcome this difficulty, we develop new technical tools for bounding such internal-collision events in the presence of quantum forward and inverse access to the public random permutation. Our result also shows that the 3-round linear SPN can be viewed as a post-quantum-secure domain-extension method for constructing a keyed pseudorandom permutation on w n bits from a random permutation on n bits.
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 Ω(22t+1tn) oracle queries to distinguish the cipher from a random permutation, whereas classically any distinguisher needs Ω(2t+1tn) queries. As a corollary, we obtain a Q2 lower bound of Ω(22t(t−1)n) 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+1)2+1t(t+1), improving on the best known classical bound of O(2α′n) with α′=t+1t. The algorithm adapts quantum walk techniques to the KAC structure.
Due to their simple security assessments, permutation-based pseudo-random functions (PRFs) have become widely used in cryptography. It has been shown that PRFs using a single n-bit permutation achieve n/2 bits of security, while those using two permutation calls provide 2n/3 bits of security in the classical setting. This paper studies the security of permutation-based PRFs within the Q1 model, where attackers are restricted to classical queries and offline quantum computations. We present improved quantum-time/classical-data tradeoffs compared with the previous attacks. Specifically, under the same assumptions/hardware as Grover’s exhaustive search attack, i.e. the offline Simon algorithm, we can recover keys in quantum time Õ(2n/3), with O(2n/3) classical queries and O(n2) qubits. Furthermore, we enhance previous superposition attacks by reducing the data complexity from exponential to polynomial, while maintaining the same time complexity. This implies that permutation-based PRFs become vulnerable when adversaries have access to quantum computing resources. It is pointed out that the above quantum attack can be applied to several cryptographic schemes, including PDMMAC and pEDM, as well as general instantiations like XopEM, EDMEM, EDMDEM, and others.
Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP.
A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance.
In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.
In this paper, we prove the security of symmetric-key constructions in an adversary model called the Q1MK model, which combines the Q1 model, where the adversary makes classical online queries and quantum offline queries, and the multi-key (multi-user) setting. Specifically, under this model, we prove the security of two symmetric-key constructions: the tweakable Even-Mansour cipher (TEM) and the FX construction (FX), as starting points for understanding the post-quantum security of symmetric-key constructions in this adversary model. Our security proofs are based on the hybrid argument technique introduced by Alagic et al. at EUROCRYPT 2022. First, we prove that in order to break TEM in the Q1MK model, Ω(2Κ/3) classical and quantum queries are needed, regardless of the number of target Κ-bit keys. Then, before turning to the Q1MK security analysis of FX, we revisit the security proof of FX in the standard Q1 model proposed in version 20230317:200508 of ePrint 2022/1097 and tighten it. By the modified proof, we show that in order to break FX with (Κ + n)-bit secret key in the Q1 model, Ω(2(Κ+n)/3) classical and quantum queries are needed. We then apply this proof to the Q1MK setting, and we show that in order to break FX in the Q1MK model, Ω(2(Κ + n - u)/3) classical and quantum queries are needed, when 2u ( 2Κ) independent keys are in use.
The security of classical symmetric-key primitives is fundamentally challenged by the emergence of quantum computing, necessitating a rigorous evaluation of their post-quantum resilience. This paper presents a comprehensive quantum circuit realization and Grover cryptanalysis of GFSPX, a lightweight block cipher featuring a 64-bit data block and a 128-bit secret key. GFSPX utilizes a unique hybrid architecture that integrates a 4-branch generalized Feistel structure with both Addition-Rotation-XOR (ARX) and Substitution-Permutation Network (SPN) components. Our quantum implementation optimizes resource distribution by exploiting the inherent reversibility of the Feistel network and employing a compact ripple-carry adder for the ARX layers. The proposed architecture achieves a qubit-optimized footprint of 209 qubits with a baseline quantum cost of 32,498 and a circuit depth of 7,617. To evaluate the cipher's resistance against quantum adversaries, we construct a parallelized Grover oracle using three plaintext-ciphertext pairs to eliminate spurious matches. Our analysis reveals that the total quantum cost of a key-recovery attack on GFSPX is 1.12×2159 quantum gates. Although this cost falls below the NIST Level 1 security threshold of 2170, the hybrid ARX-SPN design demonstrates a higher quantum attack resistance among other lightweight designs. These findings provide critical insights into the balance between classical efficiency and quantum resilience in next-generation cryptographic designs for resource-constrained environments.
Recent results on quantum cryptanalysis show that some symmetric key schemes can be broken in polynomial time even if they are proven to be secure in the classical setting. Liskov, Rivest, and Wagner showed that secure tweakable block ciphers can be constructed from secure block ciphers in the classical setting. However, Kaplan et al. showed that their scheme can be broken by polynomial time quantum superposition attacks, even if underlying block ciphers are quantum-secure. Since then, it remains open if there exists a mode of block ciphers to build quantum-secure tweakable block ciphers. This paper settles the problem in the reduction-based provable security paradigm. We show the first design of quantum-secure tweakable block ciphers based on quantum-secure block ciphers, and present a provable security bound. Our construction is simple, and when instantiated with a quantum-secure n-bit block cipher, it is secure against attacks that query arbitrary quantum superpositions of plaintexts and tweaks up to O(2n/6) quantum queries. Our security proofs use the compressed oracle technique introduced by Zhandry. More precisely, we use an alternative formalization of the technique introduced by Hosoyamada and Iwata.