A Note on Quantum-Secure PRPs

Abstract

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.

References in corpus (4)

• Breaking Symmetric Cryptosystems using Quantum Period Finding
• Quantum homomorphic encryption for circuits of low $T$-gate complexity
• Quantum-secure message authentication via blind-unforgeability
• Semantic Security and Indistinguishability in the Quantum World

Cited by in corpus (2)

• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Hardness of observing strong-to-weak symmetry breaking