General Properties of Quantum Zero-Knowledge Proofs

DOI10.1007/978-3-540-78524-8_7zbMATH Open1162.94377arXiv0705.1129OpenAlexW1518796684MaRDI QIDQ5445501FDOQ5445501

Authors: Hirotada Kobayashi 

Publication date: 5 March 2008

Published in: Theory of Cryptography (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0705.1129

Recommendations

• Zero-knowledge against quantum attacks
• Zero-knowledge against quantum attacks
• Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks
• Quantum proofs of knowledge
• Algorithms and Computation

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

• Title not available (Why is that?)
• PSPACE has constant-round quantum interactive proof systems
• Zero-knowledge against quantum attacks
• 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
• Title not available (Why is that?)
• An Unconditional Study of Computational Zero Knowledge
• Quantum Arthur-Merlin games
• Foundations of Cryptography
• The complexity of promise problems with applications to public-key cryptography
• The Knowledge Complexity of Interactive Proof Systems
• Statistical zero-knowledge languages can be recognized in two rounds
• A complete problem for statistical zero knowledge
• Title not available (Why is that?)
• Algorithms and Computation
• Title not available (Why is that?)
• Advances in Cryptology – CRYPTO 2004
• On relationships between statistical zero-knowledge proofs
• On the limits of nonapproximability of lattice problems
• Title not available (Why is that?)

Cited In (12)

• Quantum coin hedging, and a counter measure
• Complete Problem for Perfect Zero-Knowledge Quantum Proof
• Spatial Isolation Implies Zero Knowledge Even in a Quantum World
• Increasing the power of the verifier in quantum zero knowledge
• Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• Quantum protocols for zero-knowledge systems
• Zero-knowledge proof systems for QMA
• Quantum proofs of knowledge
• General properties of quantum bit commitments (extended abstract)
• On the obfuscatability of quantum point functions
• Protocols for quantum binary voting

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)