编辑“零知识证明（ZKP）”（章节）

== 沿革 ==
零知识证明最早由莎菲·戈德瓦塞尔、希尔维奥·米卡利、查尔斯·拉克福三人于1985年发表，论文题为《交互式证明系统的知识复杂度》。该论文引入交互式证明系统的'''IP'''复杂度类，并构想出“知识复杂度”概念，衡量证明过程中，由证明者传递予验证者的知识量。三人亦给出首个具体问题的零知识证明，即零知识地证明某数不是模 ''m'' 的二次剩余。连同鲍鲍伊·拉兹洛与什洛莫·莫兰的另一篇论文，戈-米-拉三氏的论文发明了交互式证明系统。为此，五人同获1993年首届哥德尔奖。

引述戈-米-拉三氏：<blockquote>该额外知识基本为0的情况尤其值得关注。我等证明，可以交互地证明某数非模 ''m'' 的二次剩余，而发布零额外知识。其出奇之处是，若不给定 ''m'' 的分解，则无高效算法判别某数是否模 ''m'' 的二次剩余。更甚者，任何已知的'''NP'''证明皆要表明 ''m'' 的素因数分解。这就表明，在证明过程中添加交互，可能减少证明某定理所必须交流的知识。 </blockquote>二次非剩余问题既有'''NP'''算法又有'''反NP'''算法，故位处'''NP'''与'''反NP'''两类之交集中。其后找到有零知识证明的若干个问题，亦具同样的性质，例如欧迪·戈德赖希未经正式出版的证明系统，可以验证某数（为两个未知素数之积）不是布卢姆整数，即并非两个模4余3的素数之积。

欧迪·戈德赖希、希尔维奥·米卡利、阿维·威格森更进一步证明，假定存在无懈可击的加密法，则可以造出三色图着色问题的零知识证明系统，而该问题本身为NP完全。又因为每个'''NP'''问题都可以高效化归成该NP完全问题，所以在前述假定下，所有'''NP'''问题皆有零知识证明。需要该假定的原因是，正如前节示例，需要有秘诺的手段。若存在单向函数，则的确有牢不可破的加密法。此为广泛引用的充分条件。另外也可能有物理方法实现。

更上一层楼，他们亦证明，图不同构问题，即图同构问题之补，有零知识证明。该问题已知属于'''反NP'''，但未知是否属于'''NP'''或其他实际可行的复杂度类。更一般地，罗素·英帕利亚佐、莫迪凯·容<sup>[译名请求]</sup>二人，与米高·本-奥尔（Michael Ben-Or）及同事，两组证明：同样假设存在单向函数或牢不可破的加密，则任何属于'''IP'''（已证等于'''PSPACE'''）的问题，皆有零知识证明。换言之，任何命题若可藉交互系统证明，则可零知识证明。

许多理论家不希望假设不必要的条件，所以试图在不假定单向函数的条件之下，证明同样的结论。有种做法称为“多证明者交互式证明系统”（见交互式证明系统），即有多个独立的证明者，而非仅得一个。验证者可以将证明者逐个孤立，然后诘问，以免被作弊证明者误导。无需任何难解假设，已可证明在此系统中，任何'''NP'''问题皆有零知识证明。

后来发现，互联网等同时执行多个协议的环境中，较难构造零知识证明。研究并发零知识证明的先驱是辛西娅·德沃克、莫尼·纳奥尔、阿米特·萨海。此类研究之中，重要成果有证据不可辨协议。与零知识相比，其性质较弱：可能有多种证据供证明者选择采用何者作证，此时仅要求验证者无法分辨证明者选择为何，但证明者可以泄漏部分信息，如全体证据组成的集合。尽管失去零知识性质，但此类协议的好处是，并发时不会遇到此前提及的问题。

变式尚有非交互式零知识证明。曼纽尔·布卢姆、保罗·费尔德曼（Paul Feldman）、米卡利证明，若证明者与验证者共有一条随机字符串，则可以达成计算零知识，而毋须交互。