CryptoDB
Quantum Advantage from OneWay Functions
Authors: 


Download:  
Conference:  CRYPTO 2024 
Abstract:  Is quantum computing truly faster than classical computing? Demonstrating unconditional quantum computational advantage lies beyond the reach of the current complexity theory, and therefore we have to rely on some complexity assumptions. While various results on quantum advantage have been obtained, all necessitate relatively stronger or less standard assumptions in complexity theory or classical cryptography. In this paper, we show quantum advantage based on several fundamental assumptions, specifically relying solely on the existence of classicallysecure oneway functions. Given the fact that oneway functions are necessary for almost all classical cryptographic primitives, our findings yield a surprising implication: if there is no quantum advantage, then there is no classical cryptography! More precisely, we introduce inefficientverifier proofs of quantumness (IVPoQ), and construct it from statisticallyhiding and computationallybinding classical bit commitments. IVPoQ is an interactive protocol between a verifier and a quantum polynomialtime prover consisting of two phases. In the first phase, the verifier is classical probabilistic polynomialtime, and it interacts with the quantum polynomialtime prover over a classical channel. In the second phase, the verifier becomes inefficient, and makes its decision based on the transcript of the first phase. If the quantum prover is honest, the inefficient verifier accepts with high probability, but any classical probabilistic polynomialtime malicious prover only has a small probability of being accepted by the inefficient verifier. In our construction, the inefficient verifier can be a classical deterministic polynomialtime algorithm that queries an NP oracle. Our construction demonstrates the following results based on the known constructions of statisticallyhiding and computationallybinding commitments from oneway functions or distributional collisionresistant hash functions:  If oneway functions exist, then IVPoQ exist.  If distributional collisionresistant hash functions exist (which exist if hardonaverage problems in $\mathbf{SZK}$ exist), then constantround IVPoQ exist. We also demonstrate quantum advantage based on worstcasehard assumptions. We define auxiliaryinput IVPoQ (AIIVPoQ) that only require that for any malicious prover, there exist infinitely many auxiliary inputs under which the prover cannot cheat. We construct AIIVPoQ from an auxiliaryinput version of commitments in a similar way, showing that  If auxiliaryinput oneway functions exist (which exist if $\mathbf{CZK}\not\subseteq\mathbf{BPP), then AIIVPoQ exist.  If auxiliaryinput collisionresistant hash functions exist (which is equivalent to $\mathbf{PWPP}\nsubseteq \mathbf{FBPP}$) or $\mathbf{SZK}\nsubseteq \mathbf{BPP}$, then constantround AIIVPoQ exist. Finally, we also show that some variants of PoQ can be constructed from quantumevaluation oneway functions (QEOWFs), which are similar to classicallysecure classical oneway functions except that the evaluation algorithm is not classical but quantum. QEOWFs appear to be weaker than classicallysecure classical oneway functions, and therefore it demonstrates quantum advantage based on assumptions even weaker than oneway functions. 
BibTeX
@inproceedings{crypto202434134, title={Quantum Advantage from OneWay Functions}, publisher={SpringerVerlag}, author={Tomoyuki Morimae and Takashi Yamakawa}, year=2024 }