Provable Post-Quantum Security of the 3-Round Substitution-Permutation Network

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.