Quantum Cryptography in Algorithmica

Abstract

We construct a classical oracle relative to which $\mathsf{P}=\mathsf{NP}$ yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds, this is a construction of pseudorandom states in "Algorithmica," and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of $\mathsf{P}$ vs. $\mathsf{NP}$ in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states. We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\ne \mathsf{QCMA}$, based on hardness of the OR $\circ$ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against $\mathsf{A}{\mathsf{C}}^0$ circuits. This variant may be of independent interest.

35 pages. V2: minor writing improvements

References in corpus (1)

• Quantum Cryptography in Algorithmica

Cited by in corpus (15)

• Quantum Cryptography in Algorithmica
• Improved Stabilizer Estimation via Bell Difference Sampling
• Efficient Unitary T-designs from Random Sums
• Efficient unitary designs and pseudorandom unitaries from permutations
• Unconditionally secure quantum commitments with preprocessing
• Quantum-Computable One-Way Functions without One-Way Functions
• Quantum Unpredictability
• A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• On Computational Complexity of Unitary and State Design Properties
• Pseudorandom Unitaries in the Haar Random Oracle Model
• Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries
• A Note on Output Length of One-Way State Generators and EFIs
• Cryptographic Characterization of Quantum Advantage
• Quantum Cryptography and Meta-Complexity