Verifiable Quantum Advantage without Structure
- URL: http://arxiv.org/abs/2204.02063v3
- Date: Mon, 11 Nov 2024 05:57:41 GMT
- Title: Verifiable Quantum Advantage without Structure
- Authors: Takashi Yamakawa, Mark Zhandry,
- Abstract summary: We replace a random oracle with a concrete cryptographic hash function such as SHA2.
We obtain plausible Minicrypt instantiations of the above results.
- Score: 15.701707809084716
- License:
- Abstract: We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: - There are NP search problems solvable by quantum polynomial-time machines but not classical probabilistic polynomial-time 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.
Related papers
- (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects.
Despite its strength, indifferentiability is not known to offer security against pre-processing attacks.
We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
arXiv Detail & Related papers (2024-10-22T00:41:47Z) - Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses.
We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
arXiv Detail & Related papers (2024-09-23T17:45:33Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
Sponge hashing is a widely used class of cryptographic hash algorithms.
Intrepid permutations have so far remained a fundamental open problem.
We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
arXiv Detail & Related papers (2024-03-07T18:46:58Z) - A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles.
We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making unboundedly many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense.
arXiv Detail & Related papers (2024-01-25T17:13:51Z) - Public-Key Encryption with Quantum Keys [11.069434965621683]
We study the notion of quantum public-key encryption (qPKE) where keys are allowed to be quantum states.
We show that computational assumptions are necessary to build quantum public-key encryption.
arXiv Detail & Related papers (2023-06-13T11:32:28Z) - Encryption with Quantum Public Keys [1.7725414095035827]
We study the question of building quantum public-key encryption schemes from one-way functions and even weaker assumptions.
We propose three schemes for quantum public-key encryption from one-way functions, pseudorandom function-like states with proof of deletion and pseudorandom function-like states, respectively.
arXiv Detail & Related papers (2023-03-09T16:17:19Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
We construct a classically succinct interactive argument for quantum computation (BQP)
Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
arXiv Detail & Related papers (2022-06-29T22:19:12Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
We construct the first fully homomorphic encryption scheme with certified deletion.
Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
arXiv Detail & Related papers (2022-03-03T10:07:32Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task.
In this work, we examine the hardness of finding such chain of PoWs against quantum strategies.
We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
arXiv Detail & Related papers (2020-12-30T18:03:56Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.