¤ OpenAccess: Green
This work has “Green” OA status. This means it may cost money to access on the publisher landing page, but there is a free copy in an OA repository.
The knowledge complexity of interactive proof-systems
Theoretical computer science
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.
Powered by Citationsy*
“The knowledge complexity of interactive proof-systems” is a paper by Sbafi Goldwasser Silvio Micali Charles Rackoff published in 1985. It has an Open Access status of “green”. You can read and download a PDF Full Text of this paper here.