Certified everlasting zero-knowledge proof for QMA
From MaRDI portal
Abstract: In known constructions of classical zero-knowledge protocols for NP, either of zero-knowledge or soundness holds only against computationally bounded adversaries. Indeed, achieving both statistical zero-knowledge and statistical soundness at the same time with classical verifier is impossible for NP unless the polynomial-time hierarchy collapses, and it is also believed to be impossible even with a quantum verifier. In this work, we introduce a novel compromise, which we call the certified everlasting 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. If the certificate is valid, even unbounded malicious verifier can no longer learn anything beyond the validity of the statement. We construct a certified everlasting zero-knowledge proof for QMA. For the construction, we introduce a new quantum cryptographic primitive, which we call commitment with statistical binding and certified everlasting hiding, where the hiding property becomes statistical once the receiver has issued a valid certificate that shows that the receiver has deleted the committed information. We construct commitment with statistical binding and certified everlasting hiding from quantum encryption with certified deletion by Broadbent and Islam [TCC 2020] (in a black box way), and then combine it with the quantum sigma-protocol for QMA by Broadbent and Grilo [FOCS 2020] to construct the certified everlasting zero-knowledge proof for QMA. Our constructions are secure in the quantum random oracle model. Commitment with statistical binding and certified everlasting hiding itself is of independent interest, and there will be many other useful applications beyond zero-knowledge.
Recommendations
Cites work
- A Tight High-Order Entropic Quantum Uncertainty Relation with Applications
- Advances in Cryptology – CRYPTO 2004
- Algorithms and Computation
- Classical binding for quantum commitments
- Everlasting multi-party computation
- How to record quantum queries, and applications to quantum indifferentiability
- scientific article; zbMATH DE number 1775425 (Why is no real title available?)
- Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model
- Multi-theorem designated-verifier NIZK for QMA
- Non-interactive classical verification of quantum computation
- Non-interactive zero-knowledge arguments for QMA, with preprocessing
- On the round complexity of secure quantum computation
- Post-quantum zero knowledge in constant rounds
- QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
- Quantum bit commitment with application in quantum zero-knowledge proof (extended abstract)
- Quantum encryption with certified deletion
- Quantum encryption with certified deletion, revisited: public key, attribute-based, and classical communication
- Quantum security proofs using semi-classical oracles
- Random oracles in a quantum world
- Revocable Quantum Timed-Release Encryption
- The Knowledge Complexity of Interactive Proof Systems
- The round complexity of quantum zero-knowledge
- Theory of Cryptography
Cited in
(18)- Complete Problem for Perfect Zero-Knowledge Quantum Proof
- Classically verifiable NIZK for QMA with preprocessing
- Public key encryption with secure key leasing
- Cloning games: a general framework for unclonable primitives
- Publicly-verifiable deletion via target-collapsing functions
- Cryptography with certified deletion
- Revocable cryptography from learning with errors
- Weakening assumptions for publicly-verifiable deletion
- Publicly verifiable deletion from minimal assumptions
- Certified everlasting secure collusion-resistant functional encryption, and more
- Software with certified deletion
- Secret sharing with certified deletion
- Zero-knowledge proof systems for QMA
- Revocable quantum digital signatures
- Secret sharing with publicly verifiable deletion
- Untelegraphable encryption and its applications
- Publicly verifiable deletion: general compilers from minimal assumptions
- Certified everlasting secure collusion-resistant functional encryption, and more
This page was built for publication: Certified everlasting zero-knowledge proof for QMA
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097264)
