The Knowledge Complexity of Interactive Proof Systems
Lists
Only you see this
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.
BibTeX
@article{goldwasser1989knowledge,
author = {Shafi Goldwasser and Silvio Micali and Charles Rackoff},
title = {{The Knowledge Complexity of Interactive Proof Systems}},
journal = {SIAM Journal on Computing},
year = {1989},
url = {https://openreview.net/forum?id=LUFllsUOogj},
}Loading related content...