The knowledge complexity of interactive proof systems

Reviewer: Violet R. Syrotiuk

An important contribution of this paper is a refined definition of zero-knowledge protocols and proof systems. Saying that a language L is in NP is equivalent to saying that there is a polynomial-time proof system for L . An interactive proof system allows the prover and the verifier to flip unbiased secret coins and to interact. An interactive proof system for a language is zero-knowledge if the prover does not give the verifier any information that the verifier could not have computed for itself, even if the verifier tries to cheat or trick the prover into revealing something. The proofs that the languages of quadratic residuosity (QR) and nonresiduosity (QNR) both have zero-knowledge interactive proof systems are the main technical contributions of this paper. These are the first zero-knowledge protocols demonstrated for languages not known to be recognizable in probabilistic polynomial time. The authors provide some brief number theory background of QR and QNR in preparation for the detailed protocols and proofs. The most interesting related work is the Arthur-Merlin game—a restricted interactive proof system in which the prover sees the coin flips of the verifier. The authors conjecture that the ability to make secret random choices is crucial for recognizing languages in zero-knowledge although it does not help to recognize more languages. The main motivation and applications of zero-knowledge protocols and proof systems are in the area of cryptographic protocols.