A classical proof of quantum knowledge for multi-prover interactive proof systems

• URL: http://arxiv.org/abs/2503.13699v1
• Date: Mon, 17 Mar 2025 20:16:22 GMT
• Title: A classical proof of quantum knowledge for multi-prover interactive proof systems
• Authors: Anne Broadbent, Alex B. Grilo, Nagisa Hara, Arthur Mehta,
• Abstract summary: In a proof of knowledge (PoK) a verifier becomes convinced that a prover possesses privileged information.<n>We extend the concept of a PoK in the setting of a single classical verifier and two quantum provers, and exhibit the PoK property for a non-local game for the local Hamiltonian problem.<n>Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state and the prover's strategy, the verifier also certifies a local quantum state.
• Score: 1.5749416770494706
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs are an important part of secure protocols such as digital signature schemes and authentication schemes as they enable a prover to demonstrate possession of a certain piece of information (such as a private key or a credential), without revealing it. Formally, A PoK is defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to the prover. We extend the concept of a PoK in the setting of a single classical verifier and two quantum provers, and exhibit the PoK property for a non-local game for the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers' strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state and the prover's strategy, the verifier also certifies a local quantum state. This technique thus provides a method to ascertain that a prover has access to a quantum system, in particular, a ground state, thus indicating a new level of verification for a proof of quantumness.

Related papers

• Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States [0.0]
  We turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol. We provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing additional information.
  arXiv  Detail & Related papers  (2023-03-02T18:38:15Z)
• 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)
• On Zero-Knowledge Proofs over the Quantum Internet [0.0]
  This paper presents a new method for quantum identity authentication (QIA) protocols. The logic of classical zero-knowledge proofs (ZKPs) due to Schnorr is applied in quantum circuits and algorithms.
  arXiv  Detail & Related papers  (2022-12-06T14:57:00Z)
• 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)
• Certified Everlasting Zero-Knowledge Proof for QMA [10.973034520723957]
  We introduce a novel compromise, which we call the certified zero-knowledge proof for QMA. It is a computational zero-knowledge proof for QMA, but the verifier issues a classical certificate that shows that the verifier has deleted its quantum information. We construct a certified everlasting zero-knowledge proof for QMA.
  arXiv  Detail & Related papers  (2021-09-29T03:05:44Z)
• Sample-efficient device-independent quantum state verification and certification [68.8204255655161]
  Authentication of quantum sources is a crucial task in building reliable and efficient protocols for quantum-information processing. We develop a systematic approach to device-independent verification of quantum states free of IID assumptions in the finite copy regime. We show that device-independent verification can be performed with optimal sample efficiency.
  arXiv  Detail & Related papers  (2021-05-12T17:48:04Z)
• Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
  We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model. This yields the first post-quantum succinct argument system from any falsifiable assumption.
  arXiv  Detail & Related papers  (2021-03-15T05:09:17Z)
• 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)
• Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
  We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values. We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
  arXiv  Detail & Related papers  (2018-03-10T05:31:38Z)

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.