The Knowledge Complexity of Interactive Proof-Systems
URL: https://dl.acm.org/doi/10.1145/22145.22178 Authors: Shafi Goldwasser, Silvio Micali, Charles Rackoff
Abstract
Usually, a proof of a theorem contains more knowledge than the mere fact that the theorem is true. For instance, to prove that two graphs are isomorphic one exhibits an isomorphism. In this paper we study how much extra knowledge need to be communicated in order to carry out an interactive proof. The notion of zero-knowledge interactive proof-systems is introduced as a proof system in which the verifier learns nothing except the truth of the theorem. Theorems about quadratic residuosity can be proven in zero-knowledge. We introduce the concept of “knowledge complexity” as a measure of the amount of knowledge communicated during a proof. We show that the knowledge complexity of any problem in NP is bounded above by log .