General Properties of Quantum Zero-Knowledge Proofs

This paper studies general properties of quantum zero- knowledge proof systems. Among others, the following properties are proved on quantum computational zero-knowledge proofs:

Honest-verifier

quantum zero-knowledge equals general quantum zero-knowledge.

Public-coin

quantum zero-knowledge equals general quantum zero-knowledge.

Quantum zero-knowledge with

perfect completeness

equals general quantum zero-knowledge with imperfect completeness.

Any quantum zero-knowledge proof system can be transformed into a

three-message public-coin

quantum zero-knowledge proof system of perfect completeness with polynomially small error in soundness (hence with arbitrarily small constant error in soundness).

All the results proved in this paper are unconditional, i.e., they do not rely any computational assumptions. The proofs for all the statements are direct and do not use complete promise problems, and thus, essentially the same method works well even for quantum statistical and perfect zero-knowledge proofs. In particular, all the four properties above hold also for the statistical zero-knowledge case (the first two were shown previously by Watrous), and the first two properties hold even for the perfect zero-knowledge case. It is also proved that allowing a simulator to output “

FAIL

” does not change the power of quantum perfect zero-knowledge proofs. The corresponding properties are not known to hold in the classical perfect zero-knowledge case.