On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work
- URL: http://arxiv.org/abs/2010.11658v4
- Date: Fri, 9 Jul 2021 09:06:07 GMT
- Title: On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work
- Authors: Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, Tai-Ning Liao
- Abstract summary: We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM)
Our main technical contribution is a framework that simplifies the use of the parallel-query generalization of the compressed oracle technique for proving query complexity results.
As a concrete cryptographic application of our techniques, we prove that the "Simple Proofs of Sequential Work" proposed by Cohen and Pietrzak remains secure against quantum attacks.
- Score: 10.43571631715192
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the so-called compressed oracle technique, introduced by Zhandry
for analyzing quantum algorithms in the quantum random oracle model (QROM). To
start off with, we offer a concise exposition of the technique, which easily
extends to the parallel-query QROM, where in each query-round the considered
algorithm may make several queries to the QROM in parallel. This variant of the
QROM allows for a more fine-grained query-complexity analysis.
Our main technical contribution is a framework that simplifies the use of
(the parallel-query generalization of) the compressed oracle technique for
proving query complexity results. With our framework in place, whenever
applicable, it is possible to prove quantum query complexity lower bounds by
means of purely classical reasoning. More than that, for typical examples the
crucial classical observations that give rise to the classical bounds are
sufficient to conclude the corresponding quantum bounds.
We demonstrate this on a few examples, recovering known results (like the
optimality of parallel Grover), but also obtaining new results (like the
optimality of parallel BHT collision search). Our main target is the hardness
of finding a $q$-chain with fewer than $q$ parallel queries, i.e., a sequence
$x_0, x_1,\ldots, x_q$ with $x_i = H(x_{i-1})$ for all $1 \leq i \leq q$.
The above problem of finding a hash chain is of fundamental importance in the
context of proofs of sequential work. Indeed, as a concrete cryptographic
application of our techniques, we prove that the "Simple Proofs of Sequential
Work" proposed by Cohen and Pietrzak remains secure against quantum attacks.
Such an analysis is not simply a matter of plugging in our new bound; the
entire protocol needs to be analyzed in the light of a quantum attack. Thanks
to our framework, this can now be done with purely classical reasoning.
Related papers
- Grover's oracle for the Shortest Vector Problem and its application in
hybrid classical-quantum solvers [0.38366697175402226]
Finding the shortest vector in a lattice is a problem that is believed to be hard both for classical and quantum computers.
Finding the best classical, quantum or hybrid classical-quantum algorithms for SVP is necessary to select cryptosystem parameters that offer sufficient level of security.
Grover's search quantum algorithm provides a generic quadratic speed-up.
We analyze how to combine Grover's quantum search for small SVP instances with state-of-the-art classical solvers.
arXiv Detail & Related papers (2024-02-21T16:05:49Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
We first examine the hardness of solving various search problems by hybrid quantum-classical strategies.
We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
arXiv Detail & Related papers (2023-11-07T04:59:02Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value.
Quantum adversaries now require full-scale computers equipped with the power of NISQ.
In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
arXiv Detail & Related papers (2022-11-23T13:55:28Z) - 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) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
Two models of quantum computation: CQ_d and QC_d.
CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation.
We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
arXiv Detail & Related papers (2022-01-06T03:10:53Z) - 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 Attacks without Superposition Queries: the Offline Simon's
Algorithm [7.819565615098435]
We introduce a new quantum algorithm which uses Simon's subroutines in a novel way.
We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature.
We improve some previous superposition attacks by reducing the data complexity.
arXiv Detail & Related papers (2020-02-27T21:05:54Z)
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.