Verifiable Quantum Advantage without Structure
- URL: http://arxiv.org/abs/2204.02063v2
- Date: Fri, 17 Jun 2022 04:23:35 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: 18.816869896281666
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography [5.360892674012226]
We present a new approach to unclonable encryption via a reduction to a novel question about nonlocal quantum state discrimination.
Our main technical result is showing that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state.
We also show other implications to single-decryptor encryption and leakage-resilient secret sharing.
arXiv Detail & Related papers (2024-05-16T17:30:55Z) - 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) - 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) - Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
We show that targetcollapsing enables publiclyverifiable deletion (PVD)
We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
arXiv Detail & Related papers (2023-03-15T15:00:20Z) - 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) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
We show that cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist.
We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
arXiv Detail & Related papers (2021-03-16T20:54:12Z) - 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) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs"
We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM)
As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
arXiv Detail & Related papers (2020-09-29T08:41:53Z)
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.