A Note on Quantum-Secure PRPs
This addresses the need for quantum-resistant cryptographic primitives in cryptography and complexity theory, though it is incremental as it builds on known results.
The paper tackles the problem of constructing pseudorandom permutations (PRPs) that are secure against quantum adversaries capable of superposition queries, achieving a construction whose security relies solely on the existence of one-way functions.
We show how to construct pseudorandom permutations (PRPs) that remain secure even if the adversary can query the permutation, both in the forward and reverse directions, on a quantum superposition of inputs. Such quantum-secure PRPs have found numerous applications in cryptography and complexity theory. Our construction combines a quantum-secure pseudorandom function together with constructions of classical format preserving encryption. By combining known results, we show how to construct quantum-secure PRP in this model whose security relies only on the existence of one-way functions.