2005/11/03 by John Watrous, Watrous, John · 6 citations
Computer Science · #Blockchain Technology Applications and Security #Cryptography and Data Security #FOS: Physical sciences #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.quant-ph/0511020
openalex publication_date 2005/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper proves that several interactive proof systems are zero-knowledge against quantum attacks. This includes a few well-known classical zero-knowledge proof systems as well as quantum interactive proof systems for the complexity class HVQSZK, which comprises all problems having "honest verifier" quantum statistical zero-knowledge proofs. It is also proved that zero-knowledge proofs for every language in NP exist that are secure against quantum attacks, assuming the existence of quantum computationally concealing commitment schemes. 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.