General Properties of Quantum Zero-Knowledge Proofs
From MaRDI portal
Publication:5445501
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
- 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?)
- 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
- On relationships between statistical zero-knowledge proofs
- On the limits of nonapproximability of lattice problems
- PSPACE has constant-round quantum interactive proof systems
- 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
- Quantum Arthur-Merlin games
- Statistical zero-knowledge languages can be recognized in two rounds
- The Knowledge Complexity of Interactive Proof Systems
- The complexity of promise problems with applications to public-key cryptography
Cited in
(12)- Increasing the power of the verifier in quantum zero knowledge
- QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
- General properties of quantum bit commitments (extended abstract)
- Complete Problem for Perfect Zero-Knowledge Quantum Proof
- On the obfuscatability of quantum point functions
- Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks
- Quantum protocols for zero-knowledge systems
- Protocols for quantum binary voting
- Spatial Isolation Implies Zero Knowledge Even in a Quantum World
- Zero-knowledge proof systems for QMA
- Quantum coin hedging, and a counter measure
- Quantum proofs of knowledge
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)
