The knowledge complexity of interactive proof-systems
发表信息
最早发表于1985年，有多个版本
作者
- Shafi Goldwasser
- Silvio Micali
- Charles Rackoff
笔记
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.
通常，一个定理的证明包含的知识要比该定理成立这一事实本身更多。例如，要证明一个图是哈密顿图（Hamiltonian），只需展示其中的一个哈密顿回路（Hamiltonian tour）；然而，这似乎蕴含的知识要比单纯的哈密顿/非哈密顿这一位信息多得多。
本文发展了一种关于证明中“知识”的计算复杂性理论。零知识证明（Zero-knowledge proofs）被定义为那些除了所讨论命题的正确性外不传递任何额外知识的证明。文中给出了二次剩余（quadratic residuosity）和二次非剩余（quadratic nonresiduosity）语言的零知识证明系统的示例。这些是已知的高效可识别语言之外的第一例零知识证明。