On the Relativistic Zero Knowledge Quantum Proofs of Knowledge

• URL: http://arxiv.org/abs/2409.03635v1
• Date: Thu, 5 Sep 2024 15:50:30 GMT
• Title: On the Relativistic Zero Knowledge Quantum Proofs of Knowledge
• Authors: Kaiyan Shi, Kaushik Chakraborty, Wen Yu Kon, Omar Amer, Marco Pistoia, Charles Lim,
• Abstract summary: We study relativistic zero-knowledge quantum proof of knowledge systems with classical communication. We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(eta) for all relations in NP. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas.
• Score: 1.660294296252135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl({\eta}) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).

Related papers

• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Entropic uncertainty relations and entanglement detection from quantum designs [5.928675196115795]
  We investigate entropic uncertainty relations and entanglement detection with an emphasis on quantum measurements with design structures. We derive improved R'enyi entropic uncertainty relations for design-structured measurements. We obtain criteria for detecting multi-partite entanglement with design-structured measurements.
  arXiv  Detail & Related papers  (2023-12-15T13:11:00Z)
• Quantitative bounds to propagation of quantum correlations in many-body systems [0.0]
  We establish limits to bipartite quantum correlations in many-body systems. Results confirm that proliferation of classical information in the Universe suppresses quantum correlations.
  arXiv  Detail & Related papers  (2023-10-04T00:24:06Z)
• 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)
• 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)
• On the Concurrent Composition of Quantum Zero-Knowledge [11.09538194395154]
  We study the notion of zero-knowledge secure against quantum-time verifiers (referred to as quantum zero-knowledge) in the concurrent composition setting. Our result yields a proof of quantum knowledge system for QMA with better parameters than prior works.
  arXiv  Detail & Related papers  (2020-12-05T23:09:29Z)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $epsilon$-zero-knowledge against quantum attacks. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier.
  arXiv  Detail & Related papers  (2020-11-05T05:40:05Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Classical proofs of quantum knowledge [10.432041176720842]
  We define the notion of a proof of knowledge in the setting where the verifier is classical. We show that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an adversary.
  arXiv  Detail & Related papers  (2020-05-04T17:45:21Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)
• Entropic Uncertainty Relations and the Quantum-to-Classical transition [77.34726150561087]
  We aim to shed some light on the quantum-to-classical transition as seen through the analysis of uncertainty relations. We employ entropic uncertainty relations to show that it is only by the inclusion of imprecision in our model of macroscopic measurements that we can prepare a system with two simultaneously well-defined quantities.
  arXiv  Detail & Related papers  (2020-03-04T14:01:17Z)

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.