TY - GEN
T1 - Quantum Cryptography in Algorithmica
AU - Kretschmer, William
AU - Qian, Luowen
AU - Sinha, Makrand
AU - Tal, Avishay
N1 - We thank Scott Aaronson, Chinmay Nirkhe, and Henry Yuen for insightful discussions. Part of this work was done while the authors attended the 2022 Extended Reunion for the Quantum Wave in Computing at the Simons Institute for the Theory of Computing. WK is supported by an NDSEG Fellowship. LQ is supported by DARPA under Agreement No. HR00112020023. MS is supported by a Simons-Berkeley Postdoctoral Fellowship. AT is supported by a Sloan Research Fellowship and NSF CAREER Award CCF-2145474.
PY - 2023/6/2
Y1 - 2023/6/2
N2 - We construct a classical oracle relative to which P = 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 P vs. 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 P = NP but BQP QCMA, 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 AC0 circuits. This variant may be of independent interest.
AB - We construct a classical oracle relative to which P = 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 P vs. 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 P = NP but BQP QCMA, 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 AC0 circuits. This variant may be of independent interest.
KW - Forrelation
KW - oracles
KW - pseudorandom quantum states
UR - http://www.scopus.com/inward/record.url?scp=85163071638&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85163071638&partnerID=8YFLogxK
U2 - 10.1145/3564246.3585225
DO - 10.1145/3564246.3585225
M3 - Conference contribution
AN - SCOPUS:85163071638
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1589
EP - 1602
BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
A2 - Saha, Barna
A2 - Servedio, Rocco A.
PB - Association for Computing Machinery
T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023
Y2 - 20 June 2023 through 23 June 2023
ER -