Physics – Quantum Physics
Scientific paper
2007-05-08
Physics
Quantum Physics
33 pages
Scientific paper
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.
No associations
LandOfFree
General Properties of Quantum Zero-Knowledge Proofs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with General Properties of Quantum Zero-Knowledge Proofs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General Properties of Quantum Zero-Knowledge Proofs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-153905