跳转到内容
← 返回计算理论
计算理论当代约 22 分钟阅读

Goldreich–Micali–Wigderson 1986：NP 里每个语言怎样都有计算零知识证明

Proofs that Yield Nothing But Their Validity

Goldreich–Micali–WigdersonGMW零知识NP图三着色FOCS 1986

1986 年 10 月，第二十七届计算机科学基础年会（FOCS）在多伦多举行。以色列理工学院、海法的奥德·戈德赖希（Oded Goldreich），麻省理工学院计算机科学实验室、剑桥马萨诸塞的西尔维奥·米卡利（Silvio Micali），与耶路撒冷希伯来大学的阿维·维格德森（Avi Wigderson）发表《Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems》，页码 174 至 187。DOI 为 10.1109/SFCS.1986.47。本页的对象是这份已印行的十四页会议论文：在标准密码学假设下——存在比特承诺，因而通常也承认单向函数存在——$NP$ 里的每一个语言都拥有计算零知识交互证明。课堂所称「GMW 一九八六年」，封面钉在这份 FOCS 文本上。它不是人物评传，也不是后来非交互简洁证明或链上验证产品的说明书。

1991 年 7 月《Journal of the ACM》第 38 卷第 3 期页码 691 至 729、DOI 为 10.1145/116825.116852 的同名长文，是同一条定理的期刊全文，不是第二份封面。期刊补上会议录里放不下的论证细节，并不另证一条新的完备性。把「一九八六年那篇」与「一九九一年那篇」收成两次发现，会把一次印刷的扩写听成两条定理。

封面是 1986 年这份十四页，不是 1985 年 5 月普罗维登斯第十七届 STOC 页码 291 至 304 的戈德瓦塞尔–米卡利–拉科夫交互证明摘要。那十四页 DOI 为 10.1145/22145.22178，作者名单里有戈德瓦塞尔、米卡利与拉科夫，没有戈德赖希与维格德森。它交出知识复杂度的定义，并把非平凡例子停在二次非剩余，并不证明整个 $NP$ 都有零知识。封面更不是 1987 年 5 月纽约第十九届 STOC 页码 218 至 229、DOI 为 10.1145/28395.28420 的戈德赖希–米卡利–维格德森《How to Play ANY Mental Game》。那十二页是诚实多数下的博弈编译器，把本页已经造好的零知识当成螺丝，去钉住「下一消息必须按说明书计算」。把两份封面收成一句，会把 $NP$ 上的传证完备性与任意博弈的编译器焊成一次页码。

它也不是同一本 1986 年 FOCS 会议录里姚期智的《How to Generate and Exchange Secrets》。那一篇写在页码 162 至 167，DOI 为 10.1109/SFCS.1986.25，对象是两方混淆电路，把门的真值表藏进密文。同卷相邻，作者、装置与量词都不同。它不是 1986 年 10 月《Journal of the ACM》第 33 卷第 4 期页码 792 至 807 的戈德赖希–戈德瓦塞尔–米卡利随机函数论文：那十六页铺的是可询问函数族，作者名单里有戈德瓦塞尔，产品是函数不是证明对话。它不是 1984 年 4 月《计算机与系统科学杂志》第 28 卷第 2 期页码 270 至 299 的戈德瓦塞尔–米卡利概率加密。那三十页问的是公钥密文在多项式观察者面前必须像随机对象。它也不是 1982 年芝加哥 FOCS 的陷门函数论文。本页不提供如何装配简洁证明产品、如何把对话搬上区块链、如何去攻一台已部署零知识系统的步骤。

它不是 密码学基础 总览，也不是 交互式证明与零知识 的学科地图。总览已经把「整个 $NP$ 都有计算零知识」收成一格；本页只抽出 1986 年这一枚钉子。它不是 沙菲·戈德瓦塞尔 的人物页。戈德瓦塞尔出现在 1985 年的定义与 1984 年的概率加密里，并不出现在本页作者名单中。它不是 随机算法 总览，也不是 计算复杂性 的 $P$ 对 $NP$ 地图。

破除误解：整个 NP 的零知识不是 1985 年的定义，也不是无限算力下的绝对静默

第一种最快的读法是：把戈德赖希–米卡利–维格德森听成 1985 年那十四页知识复杂度，或听成 1987 年那十二页心智博弈。一九八五年戈德瓦塞尔、米卡利与拉科夫合写的是定义：额外知识用真实对话与模拟器文本的不可区分来计量，非平凡例子停在二次非剩余，作者名单里有戈德瓦塞尔。他们自己把「有没有 $NP$ 完全语言落在对数知识复杂度里」列为未决。一九八六年三人合写的正是去填那条未决：在承诺假设下，每个 $NP$ 语言都有计算零知识。一九八七年三人合写的是另一件东西：一局本需要公正裁判的不完备信息博弈，怎样改写成没有裁判、只靠多数诚实玩家的协议。零知识在 1987 年是螺丝，在本页是封面。把三份印刷收成一句，会把定义、完备性与编译器焊成一次页码。

第二层误解把「零知识」听成统计上或完美意义上的绝对静默，或听成已经不需要任何密码学假设。二次非剩余那条例子可以在不依赖未证困难性的口径下写成知识复杂度为零；本页不能。图三着色的对话要先把每种颜色扣进承诺串。承诺对多项式时间的观察者隐藏内容，对无限算力的观察者不必隐藏。模拟器造出的文本与真实对话只对多项式区分者不可分，并不在统计距离上等同。把本页听成「连全能验证者也看不见着色」，会把计算零知识收成完美零知识。假设写在条件句的前件里：若比特承诺存在，模块就存在。十四页并不证明单向函数存在。

第三层误解把 1991 年期刊听成第二条定理。会议录已经写出全称量词：每个 $NP$ 语言。期刊把承诺、模拟与归约铺开，对象仍是同一句话。本页的书目钉在 1986 年页码 174 至 187；1991 年只作为同一定理的全文出现在参考文献里。

第四层误解把「打开一条边」听成已经交出整张着色，或听成一份检测作弊、还原私钥、拆开已部署协议的日程。概念只走到三步。承诺把每个顶点的颜色扣住，验证者尚未看见调色盘。打开一条边上的两个端点，只核对这些端点颜色不同，并不把其余顶点的承诺打开。模拟器并不持有一张合法着色；它猜测验证者将点哪一条边，把那两个端点写成不同颜色，猜错就回退再猜。这句话说明「计算零知识」用哪一种关系被写下，不是一份按轮次去攻击线上系统的操作单。本页也不把后来的简洁非交互证明、电路可满足性编码或链上验证器写成封面。

图三着色、比特承诺，以及计算零知识怎样铺到整个 NP

装置从「$NP$ 陈述长什么样」开始，而不是从一张产品架构图开始。库克一九七一年论文 把 $NP$ 写成：是实例带着一份短证书，多项式时间的核对者看完证书就点头。图的三着色是这类陈述的标准完全问题。一张图可以三着色，当且仅当每个顶点能涂上三种颜色之一，使每条边的两端颜色不同。着色本身就是短证书。直接把着色写下来，验证者会得到整张调色盘，那是高知识的传证。本页要的是另一件事：验证者被说服「这张图可以三着色」，却得不到一份可再用的着色。

对话的货物因此不是着色，而是一串承诺与有限次打开。证明者先把每个顶点的颜色扣进承诺。承诺的计算含义是：多项式时间的验证者看不见里面的颜色，事后又不能把已扣住的颜色改口成另一种。验证者只点一条边。证明者打开这条边两个端点的承诺。验证者核对两件事：打开与承诺一致，以及两个颜色不同。相邻顶点颜色不同，正是三着色定义里那一条局部约束。整张图的合法性被拆成「任意一条边都可以拿来抽查」。抽查本身是随机算法 那一类资源：验证者的硬币决定点哪一条边，重复独立抽查则把漏网的假着色压到可忽略。硬币在这里不是为了把期望运行时间压低，而是为了让可靠性落在概率量词里。

计算零知识落在模拟器上，不落在「打开得足够少」这句口语上。真实对话是：一份对全部顶点的承诺，加上被点中的那两个颜色。模拟器没有合法着色。它猜测挑战将落在哪一条边，只保证那两个端点颜色不同，其余承诺可以是任意可打开的填充。若后来看见的挑战与猜测一致，它交出这段文本；若不一致，它回退，换一条边再猜。多项式时间的区分者分不开「真有着色的证明者」与「只是猜对了挑战的模拟器」，前提是承诺本身对这类区分者隐藏未打开的槽。隐藏若只对多项式观察者成立，零知识就是计算的。二次非剩余那条例子可以让模拟器在统计口径上重造对话；本页的教具做不到这一点，也并不假装做到。

全称量词从一张图走到整个 $NP$，靠的是完全性，而不是为每个语言各写一套问答。任意 $NP$ 语言的是实例，都可以在多项式时间内被改写成一张图，使原实例为真当且仅当这张图可三着色。在改写成的图上跑上述对话，验证者被说服的是原语言的成员资格，看见的仍只是承诺与一条边的局部颜色。归约本身是公开的多项式手续，不额外泄露证书。计算复杂性 提供完全性与多项式时钟；十四页把这两样钉在「一种完全语言上的零知识」上，并不裁决 $P$ 对 $NP$。封面的教具停在三着色：短证书留在对话里，而不变成可读的答案纸。

承诺串从哪里来，属于条件句的前件。课堂后来把比特承诺收成「单向函数存在则承诺存在」这一档；一九八六年文本吃的是当时可用的承诺装置。沿姚期智一九八二年陷门函数论文 往下传的，是「多项式测试者分不开」这一句。存在性到此为止。它不写承诺方案的参数表，也不写如何把一次打开改造成攻击。

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

它证明了：若存在安全的比特承诺，则每个 $NP$ 语言都拥有计算零知识交互证明。它给出图三着色上的标准教具：承诺扣住着色，验证者点一条边，打开的两端颜色必须不同。它给出模拟器的存在性口径：猜测挑战边、回退再猜，使多项式观察者分不开真实对话与重造文本。它把 1985 年停在代数语言上的非平凡例子，升级成对整个短证书类的全称量词。承诺负责未打开的槽对多项式观察者隐藏，模拟负责把对话上的优势送回「没有多知道」。承诺串在统计上远不是绝对静默，计算上却可以分不开。

它没有证明单向函数存在，也没有重写 1985 年的知识复杂度定义，更没有裁决 $P$ 对 $NP$。十四页是条件句：若承诺在那儿，模块就在那儿。它没有给出二次非剩余上那条不依赖未证假设的对话，那一条属于戈德瓦塞尔–米卡利–拉科夫一九八五年论文。它没有覆盖 1987 年那条诚实多数编译器，尽管编译器把本页当成螺丝。它没有覆盖同一本 FOCS 会议录里姚期智的两方混淆电路。它没有给出对已部署协议的区分步骤，也没有把「打开一条边」写成一份选择输入攻击日程。它更没有把后来的非交互简洁证明、电路可满足性产品或链上验证器写成 1986 年的对象。限度还写在观察者类别上：计算零知识不对无限算力说话。对照属于 计算复杂性 地图与 密码学基础 总览。本页把完备性写成一次带承诺假设的条件句。

跨域连接

  • 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：那十四页把额外知识写成真实对话与模拟器文本的不可区分，对象是传证，非平凡例子停在二次非剩余。本页继承同一口径，把对象从一条代数语言换成整个 $NP$。没有 1985 年的模拟器，1986 年少了「零知识」的量词；没有本页的三着色教具，定义仍停在未决清单里。把两篇听成一次印刷，会把定义问题收成完备性问题。
  • 戈德赖希–米卡利–维格德森一九八七年论文：那十二页把任意不完备信息博弈编译成诚实多数协议。下一消息是否按说明书计算，恰好是一个 $NP$ 陈述；本页保证这类陈述可以有计算零知识证明。1987 年调用本页，并不重证全称量词。把 1986 年听成已经在编译博弈，会把传证模块收成多方产品。
  • 库克一九七一年论文：书里的短证书是高知识的传证。三着色的着色、回路的顶点序列，都是这类证书。直接写下来会把答案交出去。本页把同一份 $NP$ 证据留在承诺与局部打开里，使成员资格可被说服而不变成调色盘。没有短证书类，就没有「整个 $NP$」可铺；没有零知识，短证书就仍是高知识。
  • 交互式证明与零知识：总览页管公开硬币、多项式空间上界与后来的概率可验证明。本页只抽出 1986 年这一格：计算零知识在承诺假设下覆盖整个 $NP$。后来的非交互与简洁证明是地图上的后话，不是页码 174 至 187。把本页听成已经给出链上验证器，会把会议论文收成产品手册。
  • 密码学基础：总览需要单向函数、不可区分、承诺与零知识。本页提供把承诺焊进传证的那一次：隐藏负责未打开的颜色，打开负责局部约束，模拟负责多项式观察者没有多知道。它没有把轮次写成步骤。
  • 姚期智一九八二年陷门函数论文：芝加哥那十二页把计算不可区分写成密码学与发生器共用的装置。本页继承「多项式测试者分不开」这一句，把测试者升级成想从证明对话里抽出着色的验证者。没有不可区分语言，模拟器交不出可陈述的零知识；没有本页的完全语言，陷门仍停在假硬币一侧。
  • 姚期智：1986 年同一本 FOCS 会议录里，混淆电路把任意布尔电路编译成两方求值，页码 162 至 167。本页的对象是证明对话，不是求值电路。
  • 戈德赖希–戈德瓦塞尔–米卡利一九八六年论文：那十六页铺的是可询问函数族，产品是函数不是证明。把两篇听成一次印刷，会把树与三着色叠成一句。
  • 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把密文写成多项式不可区分。本页把同一口径搬到证明文本，货物从明文换成着色之外的一切。
  • 沙菲·戈德瓦塞尔：人物页管语义安全与知识复杂度。本页作者名单里没有戈德瓦塞尔。把 1986 年听成 GMR 的续集，会把定义者与完备性证明者焊成同一行签名。
  • 随机算法：验证者的硬币用来抽边，模拟器的硬币用来猜边。两种硬币都不以压低渐近时间为目标。

参考文献

  1. Oded Goldreich, Silvio Micali & Avi Wigderson, "Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems", Proceedings of the 27th Annual Symposium on Foundations of Computer Science, Toronto, October 1986, pp. 174–187. DOI: 10.1109/SFCS.1986.47. —— 本文对象。
  2. Oded Goldreich, Silvio Micali & Avi Wigderson, "Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems", Journal of the ACM 38(3), July 1991, pp. 691–729. DOI: 10.1145/116825.116852. —— 同一条定理的期刊全文，不是第二份封面。
  3. 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. —— 零知识定义的先行文本，例子停在二次非剩余。
  4. Oded Goldreich, Silvio Micali & Avi Wigderson, "How to Play ANY Mental Game, or A Completeness Theorem for Protocols with Honest Majority", Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, 1987, pp. 218–229. DOI: 10.1145/28395.28420. —— 诚实多数编译器，把本页当成螺丝，不是封面。
  5. Andrew C. Yao, "How to Generate and Exchange Secrets", Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986, pp. 162–167. DOI: 10.1109/SFCS.1986.25. —— 同一本 FOCS 会议录里的两方混淆电路邻居。
  6. Andrew C. Yao, "Theory and Application of Trapdoor Functions", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 80–91. DOI: 10.1109/SFCS.1982.45. —— 不可区分语言与陷门的先行文本。
  7. Shafi Goldwasser & Silvio Micali, "Probabilistic Encryption", Journal of Computer and System Sciences 28(2), April 1984, pp. 270–299. DOI: 10.1016/0022-0000(84)90070-9. —— 密文上的不可区分邻居。
  8. Oded Goldreich, Shafi Goldwasser & Silvio Micali, "How to Construct Random Functions", Journal of the ACM 33(4), October 1986, pp. 792–807. DOI: 10.1145/6490.6503. —— 作者重叠的函数族邻居，不是证明对话。
  9. 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$ 证据。

延伸阅读

正文中引用本条 · 7