ϟ

DOI: 10.1145/22145.22178

¤ 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

## Sbafi Goldwasser,Silvio Micali,Charles Rackoff

Computer science

Proof complexity

Theoretical computer science

1985

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.

- MLA
- APA
- Chicago
- IEEE
- Harvard
- BibTeX

Cite this:

Generate Citation

“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.