Zero-knowledge against quantum attacks

This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich-Micali-Wigderson classical zero-knowledge protocols for Graph Isomorphism and Graph 3-Coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive protocol for a complete problem for the complexity class of problems having "honest verifier" quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: QSZK = QSZK HV . Previously no non-trivial proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest-verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.

Authors

• John Watrous

Keywords

• quantum cryptography
• zero-knowledge proof systems