General Properties of Quantum Zero-Knowledge Proofs
From MaRDI portal
Abstract: This paper studies the complexity classes QZK and HVQZK of problems having a quantum computational zero-knowledge proof system and an honest-verifier quantum computational zero-knowledge proof system, respectively. The results proved in this paper include: (a) HVQZK = QZK, (b) any problem in QZK has a public-coin quantum computational zero-knowledge proof system, (c) any problem in QZK has a quantum computational zero-knowledge proof system of perfect completeness, and (d) any problem in QZK has a three-message public-coin quantum computational zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. All the results above are unconditional and do not rely any computational assumptions. For the classes QPZK, HVQPZK, and QSZK of problems having a quantum perfect zero-knowledge proof system, an honest-verifier quantum perfect zero-knowledge proof system, and a quantum statistical zero-knowledge proof system, respectively, the following new properties are proved: (e) HVQPZK = QPZK, (f) any problem in QPZK has a public-coin quantum perfect zero-knowledge proof system, (g) any problem in QSZK has a quantum statistical zero-knowledge proof system of perfect completeness, and (h) any problem in QSZK has a three-message public-coin quantum statistical zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. It is stressed that our proofs are direct and do not use complete promise problems or those equivalents. This gives a unified framework that works well for all of quantum perfect, statistical, and computational zero-knowledge proofs, and enables us to prove properties even on the computational and perfect zero-knowledge proofs for which no complete promise problems are known.
Recommendations
Cites work
- A complete problem for statistical zero knowledge
- Advances in Cryptology – CRYPTO 2004
- Algorithms and Computation
- An Unconditional Study of Computational Zero Knowledge
- Foundations of Cryptography
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- scientific article; zbMATH DE number 1775425 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- scientific article; zbMATH DE number 2196514 (Why is no real title available?)
- On relationships between statistical zero-knowledge proofs
- On the limits of nonapproximability of lattice problems
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- PSPACE has constant-round quantum interactive proof systems
- Quantum Arthur-Merlin games
- Statistical zero-knowledge languages can be recognized in two rounds
- The complexity of promise problems with applications to public-key cryptography
- The Knowledge Complexity of Interactive Proof Systems
Cited in
(12)- Complete Problem for Perfect Zero-Knowledge Quantum Proof
- Quantum proofs of knowledge
- Protocols for quantum binary voting
- Increasing the power of the verifier in quantum zero knowledge
- Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks
- Quantum coin hedging, and a counter measure
- Spatial Isolation Implies Zero Knowledge Even in a Quantum World
- QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
- General properties of quantum bit commitments (extended abstract)
- Zero-knowledge proof systems for QMA
- On the obfuscatability of quantum point functions
- Quantum protocols for zero-knowledge systems
This page was built for publication: General Properties of Quantum Zero-Knowledge Proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5445501)
