Quantum Cryptography in Algorithmica

We construct a classical oracle relative to which 𝖯 = 𝖭𝖯 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 𝖯 vs. 𝖭𝖯 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 𝖯 = 𝖭𝖯 but 𝖡𝖰𝖯 ̸ = 𝖰𝖢𝖬𝖠, based on hardness of the OR∘Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against 𝖠𝖢 𝟢 circuits. This variant may be of independent interest.