The Knowledge Complexity of Interactive Proof Systems

TLDR

Proofs often contain more knowledge than the mere fact that a theorem is true, as illustrated by a Hamiltonian tour revealing more than just Hamiltonian/non‑Hamiltonian status. The paper develops a computational complexity theory of the knowledge contained in proofs. Zero‑knowledge proofs are defined as proofs that convey no additional knowledge beyond the correctness of the proposition. The authors provide zero‑knowledge proof systems for quadratic residuosity and quadratic nonresiduosity, the first such proofs for languages not known to be efficiently recognizable.

Abstract

Usually, a proof of a theorem contains more knowledge than the mere fact that the theorem is true. For instance, to prove that a graph is Hamiltonian it suffices to exhibit a Hamiltonian tour in it; however, this seems to contain more knowledge than the single bit Hamiltonian/non-Hamiltonian. In this paper a computational complexity theory of the “knowledge” contained in a proof is developed. Zero-knowledge proofs are defined as those proofs that convey no additional knowledge other than the correctness of the proposition in question. Examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity. These are the first examples of zero-knowledge proofs for languages not known to be efficiently recognizable.