TY - GEN

T1 - Verifiable Quantum Advantage without Structure

AU - Yamakawa, Takashi

AU - Zhandry, Mark

N1 - Funding Information:
We thank Scott Aaronson for helpful suggestions, including the conceptual implication of worst-case completeness. We thank anonymous reviewers of FOCS 2022 for their helpful comments. Mark Zhandry is supported in part by an NSF CAREER award.
Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: There are NP search problems solvable by BQP machines but not BPP machines. There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs. There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin. Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction. By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.

AB - We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: There are NP search problems solvable by BQP machines but not BPP machines. There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs. There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin. Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction. By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.

UR - http://www.scopus.com/inward/record.url?scp=85138231347&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85138231347&partnerID=8YFLogxK

U2 - 10.1109/FOCS54457.2022.00014

DO - 10.1109/FOCS54457.2022.00014

M3 - Conference contribution

AN - SCOPUS:85138231347

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 69

EP - 74

BT - Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022

PB - IEEE Computer Society

T2 - 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022

Y2 - 31 October 2022 through 3 November 2022

ER -