Paper 2023/161
Quantum Advantage from OneWay Functions
Abstract
Showing quantum advantage based on weaker and standard classical complexity assumptions is one of the most important goals in quantum information science. In this paper, we demonstrate quantum advantage with several basic assumptions, specifically based on only the existence of classicallysecure oneway functions. 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 $\mathbf{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: (1) If oneway functions exist, then IVPoQ exist. (2) 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 (1) If auxiliaryinput oneway functions exist (which exist if $\mathbf{CZK}\not\subseteq\mathbf{BPP}$), then AIIVPoQ exist. (2) 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 proofs of quantumnessquantum advantagecommitmentsoneway functions
 Contact author(s)

tomoyuki morimae @ yukawa kyotou ac jp
takashi yamakawa ga @ hco ntt co jp  History
 20230215: approved
 20230209: received
 See all versions
 Short URL
 https://ia.cr/2023/161
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/161, author = {Tomoyuki Morimae and Takashi Yamakawa}, title = {Quantum Advantage from OneWay Functions}, howpublished = {Cryptology ePrint Archive, Paper 2023/161}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/161}}, url = {https://eprint.iacr.org/2023/161} }