Quantum Cryptography and Meta-Complexity

• URL: http://arxiv.org/abs/2410.01369v2
• Date: Tue, 5 Nov 2024 11:43:32 GMT
• Title: Quantum Cryptography and Meta-Complexity
• Authors: Taiga Hiroka, Tomoyuki Morimae,
• Abstract summary: In classical cryptography, one-way functions (OWFs) are the minimal assumption, while it is not the case in quantum cryptography. We show that one-way puzzles (OWPuzzs) exist if and only if GapK is weakly-quantum-average-hard. We also show that if quantum PRGs exist then GapK is strongly-quantum-average-hard.
• Score: 2.6089354079273512
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In classical cryptography, one-way functions (OWFs) are the minimal assumption, while it is not the case in quantum cryptography. Several new primitives have been introduced such as pseudorandom state generators (PRSGs), one-way state generators (OWSGs), one-way puzzles (OWPuzzs), and EFI pairs. They seem to be weaker than OWFs, but still imply many useful applications. Now that the possibility of quantum cryptography without OWFs has opened up, the most important goal in the field is to build a foundation of it. In this paper, we, for the first time, characterize quantum cryptographic primitives with meta-complexity. We show that one-way puzzles (OWPuzzs) exist if and only if GapK is weakly-quantum-average-hard. GapK is a promise problem to decide whether a given bit string has a small Kolmogorov complexity or not. Weakly-quantum-average-hard means that an instance is sampled from a QPT samplable distribution, and for any QPT adversary the probability that it makes mistake is larger than ${\rm 1/poly}$. We also show that if quantum PRGs exist then GapK is strongly-quantum-average-hard. Here, strongly-quantum-average-hard is a stronger version of weakly-quantum-average-hard where the probability that the adversary makes mistake is larger than $1/2-1/{\rm poly}$. Finally, we show that if GapK is weakly-classical-average-hard, then inefficient-verifier proofs of quantumness (IV-PoQ) exist. Weakly-classical-average-hard is the same as weakly-quantum-average-hard except that the adversary is PPT. IV-PoQ are a generalization of proofs of quantumness (PoQ) that capture sampling-based and search-based quantum advantage, and an important application of OWpuzzs. This is the fist time that quantum advantage is based on meta-complexity. (Note: There are two concurrent works[Khurana-Tomer,arXiv:2409.15248; Cavalar-Goldin-Gray-Hall,arXiv:2410.04984].)

Related papers

• On the Cryptographic Foundations of Interactive Quantum Advantage [8.438148845727445]
  hardness required to achieve proofs of quantumness (PoQ)<n>In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ.
  arXiv  Detail & Related papers  (2025-10-06T17:51:22Z)
• Quantum Cryptography and Hardness of Non-Collapsing Measurements [10.237675529033163]
  One-way puzzles (OWPuzzs) are a quantum analogue of one-way functions (OWFs)<n>In this paper, we base OWPuzzs on hardness of non-collapsing measurements.<n>We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs)
  arXiv  Detail & Related papers  (2025-10-06T02:42:20Z)
• Hardness of Quantum Distribution Learning and Quantum Cryptography [11.85957541950196]
  One-way puzzles (OWPuzzs) provide a natural quantum analogue of one-way functions (OWFs)<n>In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning.
  arXiv  Detail & Related papers  (2025-07-02T02:12:38Z)
• From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation [8.093227427119325]
  Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications.<n>In this work, we initiate a study of the power of quantum iO.
  arXiv  Detail & Related papers  (2025-06-24T11:50:33Z)
• CountCrypt: Quantum Cryptography between QCMA and PP [7.408475650692233]
  We construct a quantum oracle relative to which BQP = QCMA but quantum-computation-classical-communication key exchange, QCCC commitments, and two-round quantum key distribution exist. We also show that QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles.
  arXiv  Detail & Related papers  (2024-10-18T18:04:27Z)
• Cryptographic Characterization of Quantum Advantage [8.093227427119325]
  We show that inefficient-verifier of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. This is the first time that a complete cryptographic characterization of quantum advantage is obtained.
  arXiv  Detail & Related papers  (2024-10-01T08:29:25Z)
• Hard Quantum Extrapolations in Quantum Cryptography [9.214658764451348]
  We study the quantum analogues of the universal extrapolation task. We show that it is hard if quantum commitments exist, and it is easy for quantum space.
  arXiv  Detail & Related papers  (2024-09-25T00:09:42Z)
• 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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• 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)
• 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.