Goldwasser–Micali–Rackoff 1985：交互证明系统的知识复杂度怎样把零知识写成定义

破除误解：零知识不是加密，也不是「证明可以随便一点」#

第一层误解把标题听成「用更强的加密把证据藏起来」。加密的目标是传递内容，只是内容对旁观者不可读。本页的目标是根本不把内容当作必须交付的货物。形式标准是模拟：若多项式时间的验证者自己就能生成与真实对话不可区分的文本，他就没有从证明者那里得到可计算的新东西。香农互信息在这里不够用。随机串对听者是信息，却可以是零知识，因为他家里也能抛硬币。把零知识听成密文，会把 1985 年的知识度量收成 1949 年的保密量。

第二层误解把「概率的、要问答的证明」听成课堂上的不严格。完备性要求真命题以压倒性概率被接受，可靠性要求假命题对任意作弊证明者都以压倒性概率被拒绝。错误界写成对每个常数 $k$、对足够长的输入小于 $n^{-k}$，概率只算验证者自己的硬币。验证者不必信任对面是谁，只须信任自己的随机带。这与「某一类常见作弊手法会被抓住」不是同一句话。坚持零错误在这里不是严谨，而是拒绝一种已经被写成量词的证明观念。

第三层误解把 1985 年听成后来整张地图。原文没有证明交互类等于多项式空间，没有把证明摊成只读常数比特的编码，也没有证明每个 $NP$ 语言都有计算零知识。他们自己把「有没有 $NP$ 完全语言落在对数知识复杂度里」列为未决。图同构的课堂例子是后来的教具；本页钉住的语言是二次非剩余，另点布卢姆的那一类整数。把总览页的谱系提前写进这十四页，会把一次定义收成一部学科史。

第四层误解把「知识」听成模态逻辑里的可能世界，或听成「验证者连真假那一比特也不知道」。法金、哈尔彭、瓦尔迪与摩西讨论的是全能主体对私有事件的知识。戈德瓦塞尔、米卡利与拉科夫改成：知识相对于指定的计算资源，对象是双方都看得见的公共输入。知识复杂度量的是额外知识。属于语言这一事实正是证明系统本来要交付的那一比特；零知识说的是对话文本对其余多项式时间问题没有用。把 $KC(0)$ 听成「什么都没发生」，会把证明的目的一并删掉。

交互图灵机、知识复杂度，以及二次非剩余#

装置从交互图灵机开始。每台机器有只读输入带、工作带、只能从左往右扫的随机带，外加一条只读通信带与一条只写通信带。写头只能在空白格上向右写。两台机器组成有序对 $(A,B)$：共享同一条输入，并把对方的只写带当作自己的只读带。$B$ 先开始，双方轮流主动，任一方可在自己的回合里终止。第 $i$ 条消息是该回合写下的整串。一次计算的文本是双方消息的交错序列。全体文本构成概率空间，概率来自两台机器的硬币。这就是他们说的「课堂上能追问的证明」，对照 库克一九七一年论文 里那种「可以印在书里的证明」：$NP$ 的证明者一次性写下短证书，验证者确定性核对。这里的证明者计算力不限，验证者必须多项式时间。

$(A,B)$ 是语言 $L$ 的交互证明系统，当且仅当两条成立。若 $x\in L$，诚实的 $A$ 让 $B$ 以至少 $1-n^{-k}$ 的概率接受。若 $x\notin L$，则对任意机器 $A'$，$B$ 接受的概率至多 $n^{-k}$。强调落在「是」实例上：在语言里要能证明，不在语言里则谁也证明不成。他们把拥有这种系统的语言类记作 $IP$，用 $IP[f(n)]$ 记下回合数，用证明者的时间界再切一刀。对照就在同一届 STOC：巴巴伊的亚瑟–梅林游戏让梅林看见亚瑟的全部硬币，因而公开硬币、常数轮往往够用。戈德瓦塞尔三人允许验证者把硬币藏起来，并相信包含是真包含，也相信回合数的层级不会塌缩。帕帕季米特里乌同年前后的「与自然对弈」把多项式空间写成另一种博弈，他们点明那不是一种有效的传证方法。私有硬币后来被证明并不本质，交互能走多远也要另文才收口。那些修正属于后话，不是 1985 年的定理。

知识被写成分布之间的可区分度。对每个输入 $x$，真实对话给出一串文本的总体；模拟器 $M$ 给出另一串。区分者是多项式时间的概率算法，输出一比特。$A$ 向 $B$ 至多交付 $f(n)$ 比特知识，当且仅当存在多项式时间的 $M$，使两总体至多 $1-2^{-f(n)}$ 可区分；并且这句话必须对任意多项式时间的作弊验证者 $B'$ 成立。$f=0$ 时就是不可区分。随机比特、多项式时间自己算得出的东西，都不算知识。记者与警官的比方写在原文里：若你在打字机前就能生成与电话里同样的对话，就不必打电话。语言 $L$ 的知识复杂度是 $f(n)$，记作 $L\in KC(f(n))$，当它拥有一个交互证明系统，且把输入限制在 $L$ 上时证明者至多交付 $f(n)$ 比特额外知识。$KC(0)$ 是极端：$B$ 被说服 $x\in L$，但文本对多项式时间计算来说，在任何其他用途上都可被不依赖 $A$ 的机器重造。$P$、$RP$、$BPP$ 平凡地在 $KC(0)$ 里。若 $L$ 本身不在概率多项式时间里，任何把证书一次性写下来的 $NP$ 证明都不可能是零知识——平方根、哈密顿回路、素因子，本身就是额外知识。

他们给出的非平凡例子是二次非剩余。令 $L=\{(y,m)\mid y$ 与 $m$ 互素且 $y$ 不是模 $m$ 的平方$\}$。素因子已知则判定平凡；因子未知则没有已知的多项式手续。高斯《算术研究》把二次剩余性与素性、分解、丢番图方程并列为四大问题。雅可比符号可在多项式时间算出：等于 $-1$ 则必为非剩余；等于 $1$ 时才进入困难的一半。$L$ 其实在 $NP$ 里：证明者可以送出 $m$ 的分解。他们要的不是这张证书，而是一张不交出分解的对话。简单版已经是交互证明。验证者抛 $n$ 次硬币，每次或送随机平方，或送「随机平方再乘 $y$」，让证明者猜硬币。若 $y$ 真是非剩余，无限强的证明者能分开两类；若 $y$ 是剩余，两类在分布上叠成同一族随机平方，猜对全部硬币的概率是 $2^{-n}$。这套问答对诚实验证者已经是零额外知识：模拟器看着验证者自己的硬币就能复述。对作弊验证者则不是。对方可以把任意整数丢过来，把证明者当成剩余性神谕。第四节因而加上一道门：证明者先抽查验证者是否真知道这些数是按两种合法类型造出来的，再回答剩余性。期刊版的模拟器对同一盘硬币跑两遍，用两次不同的抽查抽出类型，而不去一般地判定剩余性。门的存在性属于定义，本页不把它写成操作单。布卢姆那类「模 4 余 3 的不同素因子个数为偶数」的整数，被他们记为另一个已知的 $KC(0)$ 语言。二次非剩余的零知识不依赖未证明的复杂性假设。

它证明了什么，没有覆盖什么#

它证明了：证明可以是带硬币的对话；额外知识可以用模拟器与区分者来计量；这个量可以是零。它给出一条无条件定理：二次非剩余拥有知识复杂度为零的交互证明。它把 $NP$ 改写成「印在书里的证明」这一特例，使完全性、可靠性与验证者多项式时间三条要求在交互模型里重新可见。不可区分性沿用戈德瓦塞尔与米卡利 1984 年概率加密里的总体语言，只是对象从密文换成对话文本。概念证据到此为止。模拟器回答的是「知识在 1985 年用哪一种计算关系写下」；二次非剩余回答的是「$KC(0)$ 不是给 $BPP$ 起的别名」。两句都不是协议菜谱。

它没有证明交互类的上限。原文问 $NP$ 是否真包含于 $IP$，问 $KC(0)$ 是否落在 $NP$ 里、是否一轮就够，问 $IP[k]$ 是否严格小于 $IP[k+1]$，问有没有 $NP$ 完全语言落在对数知识复杂度里。他们当时相信私有硬币严格强于公开硬币，也相信回合层级不会塌。后来的公开硬币模拟与多项式空间上界，都不在这十四页里。把沙米尔的等式读回 1985 年，会把一份开放清单收成一条包含定理。

它没有覆盖整个 $NP$ 的零知识。把「哈密顿回路的证书泄露回路」写成动机，并不等于构造出对回路问题的零知识对话。那一步是戈德赖希、米卡利与维格德森在单向函数假设下完成的后话。本页的无条件例子停在代数语言。知识复杂度的一般定义后来也被修补过：区分度、失败概率与抽取器的量化，在会议摘要里仍有「细节见全文」的缝。期刊版补了模拟，没有把缝说成已经不存在。把 1985 年听成「零知识从此对所有短证书成立」，会把未决问题第五条从文末抹掉。

它没有覆盖概率可验证明，也没有覆盖电路下界。电路复杂度 问的是小电路能不能计算；本页问的是对话交不交额外知识。两条轴可以后来相交，1985 年并不相交。密码协议那一节把零知识用作模块化正确性的语言：子协议若只泄露规定的比特，拼装才可能被陈述。费希尔、米卡利与拉科夫据此改写拉宾的茫然传送，使其正确性回到分解困难性这一条假设上，而不再叠一条「不存在某种特殊平方」的额外公设。本页是定义的证据对象。它不提供如何隐藏口令、如何把攻击编码进对话、如何用重放去拆实现的步骤。工业系统后来借用同一组词，并不把最坏情况的定义预算作废；那是总览页与工程页的事。

跨域连接#

• 认识论：证明在这里被收成一种带错误界的交往：听者只须多项式时间，说者不必被预先信任。可靠性是对所有说者的全称量词，不是对诚实说者的存在量词。这把「我有理由相信」从心理确信改写成可检验的接受概率。神谕式的一次性证书仍然合法，只是被标明为高知识复杂度的特例。把交互听成修辞术，会把量词上的可靠性收成口才。
• 知识：盖梯尔传统追问真信念加上何种理由才配叫知识。本页把「理由」换成一份可模拟的文本：你带着「$x$ 在语言里」离开，若那份文本你自己也能造，你就没有得到额外的命题知识。停摆的钟给出真信念却没有恰当联系；零知识给出真信念，并证明其余可计算内容与证明者之间没有可利用的联系。模拟器不是心理模型，它是「没有多知道」的数学否证手段。把知识复杂度听成信息论熵，会把随机硬币算进秘密。
• 科学哲学：高斯把二次剩余性列为算术的公开问题；本页不宣称它已不在多项式时间里，只宣称存在一种传证方式，使剩余性本身不必作为证书被交出来。可证伪的是协议，不是困难性：若出现能区分真实对话与模拟器的多项式算法，零知识的断言就垮。困难性仍是候选，定义却已经是相对明确对手类的谓词。把「没有已知算法」听成「已经证明没有算法」，会把 1801 年的问题与 1985 年的定义叠成一句。
• 密码学基础：语义安全把密文写成不可区分游戏；本页把同一套总体语言搬到证明文本上。单向函数、陷门与填充回答的是「看见密文该知道什么」；知识复杂度回答的是「被说服之后还剩下什么可计算的余量」。两者都把安全写成相对算力的谓词，而不是绝对静默。把零知识听成概率加密的别名，会把传证问题收成传消息问题。模块化正确性是这条定义对协议拼装的用法，不是本页对象里的产品说明书。
• 证明：欧几里得式的证明要求从公理推出必然为真，任何人可离线复核。交互证明把必然性换成高概率，把离线换成在场追问。书里的证明必须预先回答所有问题；课堂上的证明可以等到问题出现再答。代价是：文本本身不再自动对第三方构成证据，除非把硬币公开或另做编译。把零知识听成「证明可以不严谨」，说反了：严谨被写进接受概率与模拟关系，只是不再写进一张可复印的纸。
• 可计算性：停机问题问手续是否存在；本页假定验证手续存在，并加上多项式时钟与硬币。证明者可以是不可计算的，验证者必须是可计算且高效的。可靠性因此不是「存在一台拒斥假定理的机器」，而是「没有任何机器能以不可忽略的概率骗过这台带硬币的验证者」。把二次非剩余听成不可判定，会把数论里的候选困难收成图灵度上的不可能。

参考文献#

• Shafi Goldwasser, Silvio Micali & Charles Rackoff, "The Knowledge Complexity of Interactive Proof-Systems", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, Rhode Island, 1985, pp. 291–304. DOI: 10.1145/22145.22178. —— 本文对象：交互图灵机、知识复杂度与二次非剩余的零知识证明（会议扩展摘要）。
• Shafi Goldwasser, Silvio Micali & Charles Rackoff, "The Knowledge Complexity of Interactive Proof Systems", SIAM Journal on Computing 18(1), 1989, pp. 186–208. DOI: 10.1137/0218012. —— 1989 年期刊全文，补上会议摘要里标明「细节见终稿」的模拟论证。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 论文用来对照的 $NP$ 传证模型：一次性短证书。
• László Babai, "Trading Group Theory for Randomness", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, Rhode Island, 1985, pp. 421–429. DOI: 10.1145/22145.22192. —— 同一届的亚瑟–梅林游戏，用以标明公开硬币是邻居不是封面。
• Shafi Goldwasser & Silvio Micali, "Probabilistic Encryption", Journal of Computer and System Sciences 28(2), 1984, pp. 270–299. DOI: 10.1016/0022-0000(84)90070-9. —— 总体不可区分性的前身，本页把它从密文搬到对话文本。
• Christos H. Papadimitriou, "Games Against Nature", Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983, pp. 446–450. DOI: 10.1109/SFCS.1983.20. —— 论文点名的多项式空间博弈刻画，用以标明那不是有效传证。

延伸阅读#

• 与 交互式证明与零知识 对读：总览页管公开硬币、多项式空间上界与后来的概率可验证明；本页停在 1985 年的知识度量与二次非剩余。
• 与 沙菲·戈德瓦塞尔 对读：人物页管语义安全、伪随机函数与图灵奖谱系；本页停在 GMR 这篇定义。
• 与 密码学基础 对读：先看不可区分游戏怎样成为安全谓词，再看本页怎样把同一谓词用在证明文本上。
• 与 库克一九七一年论文 对读：书里的短证书是高知识复杂度的传证；本页问证书能不能被对话替代。
• 与 计算复杂性 对读：类语言 $IP$ 属于地图；本页提供地图上「证明」一词被重写的那一枚钉子。
• 与 可计算性 对读：存在手续与多项式可验证手续是两层边界；硬币与交互加在第二层上。