The Knowledge Complexity of Interactive Proof Systems

The paper observes that a conventional proof typically contains more knowledge than the single bit stating that a theorem is true, and sets out to formalize this intuition. It develops a computational complexity theory of the knowledge contained in a proof and introduces the notion of zero-knowledge proofs, which are defined as interactive proofs that convey no additional knowledge beyond the correctness of the proposition being proved.

To demonstrate the concept, the authors construct zero-knowledge proof systems for the languages of quadratic residuosity and quadratic nonresiduosity. These were the first examples of zero-knowledge proofs for languages not known to be efficiently recognizable, and the framework became foundational to modern cryptography and complexity theory.