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

Goldreich–Micali–Wigderson 1987：任意心智博弈怎样在诚实多数下被编译成不泄露部分信息的协议

How to Play any Mental Game

Goldreich–Micali–WigdersonGMW心智博弈诚实多数完备性定理STOC 1987

1987 年 5 月，第十九届 ACM 计算理论年会（STOC）在纽约举行。以色列理工学院、海法的奥德·戈德赖希（Oded Goldreich），麻省理工学院计算机科学实验室、剑桥马萨诸塞的西尔维奥·米卡利（Silvio Micali），与耶路撒冷希伯来大学的阿维·维格德森（Avi Wigderson）发表《How to Play ANY Mental Game, or A Completeness Theorem for Protocols with Honest Majority》，页码 218 至 229。DOI 为 10.1145/28395.28420。会议录主编是阿尔弗雷德·艾霍（Alfred V. Aho），ISBN 为 0-89791-221-7。本页的对象是这份已印行的十二页会议论文：给定一局带不完备信息、玩家数目任意的博弈说明书，存在多项式时间的编译器，交出一套协议；只要诚实玩家占多数，协议就不泄露任何部分信息。课堂所称「GMW 一九八七年」，封面钉在这份 STOC 文本上。它不是人物评传，也不是安全多方计算产品说明书。

封面是 1987 年这份十二页，不是 1985 年 5 月普罗维登斯第十七届 STOC 页码 291 至 304 的戈德瓦塞尔–米卡利–拉科夫交互证明摘要。那十四页 DOI 为 10.1145/22145.22178，问的是证明对话泄露了多少额外知识，作者名单里有米卡利却没有戈德赖希与维格德森，对象是传证，不是把博弈编译成协议。封面更不是 1986 年 10 月多伦多第二十七届计算机科学基础年会（FOCS）页码 174 至 187、DOI 为 10.1109/SFCS.1986.47 的戈德赖希–米卡利–维格德森《Proofs that Yield Nothing But Their Validity》。那一篇证明的是：在合适的密码学假设下，每个 $NP$ 语言都有计算零知识证明。1991 年 7 月《Journal of the ACM》第 38 卷第 3 期页码 691 至 729 是同一条零知识定理的期刊全文。一九八六年那篇零知识论文只在正文里点名。1987 年把已经造好的零知识当成模块，用来钉住「下一消息必须按说明书计算」，并不重证「整个 $NP$ 都有零知识」。把两份封面收成一句，会把零知识完备性与博弈编译器焊成一次页码。

它也不是同一本 1986 年 FOCS 会议录里姚期智的《How to Generate and Exchange Secrets》。那一篇混淆电路写在姚期智人物页上，对象是两方、把门的真值表藏进密文，不是诚实多数下任意人数的编译器。它不是 1982 年芝加哥 FOCS 页码 80 至 91 的陷门函数论文。那十二页交出计算不可区分与发生器，并不编译一局不完备信息博弈。同一届芝加哥 FOCS 另有百万富翁问题，仍不是本页封面。它不是 1984 年 4 月《计算机与系统科学杂志》第 28 卷第 2 期页码 270 至 299 的戈德瓦塞尔–米卡利概率加密。那三十页问的是公钥密文在多项式观察者面前必须像随机对象，对象是传消息，不是多人按说明书出牌。它更不是 1986 年 10 月《Journal of the ACM》第 33 卷第 4 期页码 792 至 807 的戈德赖希–戈德瓦塞尔–米卡利随机函数论文：那十六页铺的是可询问函数族。它也不是 1988 年本-奥尔、戈德瓦塞尔与维格德森那篇不靠密码学假设、假定有私有信道的完备性定理，尽管作者名单里同样有维格德森。本页不提供如何装配多方计算产品、如何选取电路表示、如何去攻一台已部署协议的步骤。

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

破除误解：心智博弈不是已经造好的多方产品，诚实多数也不等于已经去掉假设

第一种最快的读法是：把戈德赖希–米卡利–维格德森听成 1986 年那篇「整个 $NP$ 都有零知识」，或听成 1985 年那十四页知识复杂度。一九八六年三人合写的是传证：短证书对应的语言可以在计算零知识里被说服，而不把证书交出来。一九八五年戈德瓦塞尔、米卡利与拉科夫合写的也是传证，只是例子停在二次非剩余，并未铺到整个 $NP$。一九八七年三人合写的是另一件东西：一局本需要公正裁判的不完备信息博弈，怎样改写成没有裁判、只靠多数诚实玩家的协议。零知识在这里是螺丝，不是封面。把三份印刷收成一句，会把定义、完备性与编译器焊成一次页码。

第二层误解把标题听成已经造出一款可部署的多方计算，或听成一份把混淆电路焊进产品的规格书。十二页交出的是编译器的存在性：说明书进，协议出，手续落在多项式时间里。它没有选定一种生产用的电路表示，没有给出轮密钥表，也没有比较哪一种工程优化更快。「心智」说的是没有实体纸牌、没有当面洗牌的裁判，不是一份扑克应用程序。沙米尔、里韦斯特与阿德曼较早的「心智扑克」是民俗邻居，指出远程出牌会多漏信息；本页问的是任意一局这样的博弈能不能被统一编译。

第三层误解把「诚实多数」听成可有可无的礼貌，或听成已经证明不必再要密码学假设。原文的保证带条件：多数玩家按说明书走，少数偏离不能迫使协议交出规定输出之外的部分信息。两人之局里一人作弊，诚实一方并不构成多数，因此两方恶意模型不是这句定理的直接特例。姚期智 1986 年那条混淆电路走另一条路，对象与门槛都不同。诚实多数也没有把安全从「多项式观察者分不开」改写成「无限算力也看不见」。十二页仍吃计算假设，通常落在单向函数或陷门置换这一档，沿姚期智一九八二年陷门函数论文与零知识模块往下传。后年那条不靠假设、靠私有信道的完备性定理是邻居，不是页码 218 至 229。

第四层误解把「用零知识强制下一消息」听成一份检测作弊、还原私钥、拆开已部署协议的日程。下一消息是说明书规定的函数：玩家的私有输入、自己的硬币、以及到目前为止大家都看得见的对话文本，决定下一句该说什么。这句话本身是一个 $NP$ 陈述——存在一份短证据，证明刚送出的串确实等于该函数的值。一九八六年已经说明，这类陈述可以有计算零知识证明。一九八七年只调用这条存在性：对方被说服「你按说明书算过了」，却得不到输入本身。概念证据到此为止。模拟器回答的是「部分信息在 1987 年用哪一种计算关系被禁止」；编译器回答的是「任意说明书都能被改写」。两句都不是操作单。

不完备信息、诚实多数，以及零知识怎样钉住下一消息

装置从「什么样的博弈需要裁判」开始，而不是从一张产品架构图开始。不完备信息说的是：每位玩家手里有别人不该看见的输入，像扣着的牌。规定的输出可能只是赢者是谁、每人应付多少，或某条公共函数的值。若存在一位大家都信任的裁判，事情很简单。各人把输入私下交给裁判，裁判按说明书计算，只把规定的输出发回来。心智博弈问的是：把裁判拿掉之后，只留下互相发消息的通道，同一局还能不能玩。任意人数被写进全称量词里，不是先给三人或四人各做一份特设协议。

编译器吃进去的是博弈的说明书。说明书把合法消息写成输入、硬币与已有文本的多项式时间函数，因此可以当成电路，却不必在本页展开成某一种门库。编译器吐出来的是一套新的消息来回。诚实玩家按新协议走，其计算量对原说明书的规模是多项式。被证明的不是某一种扑克的特设洗牌，而是：凡是能交给裁判的说明书，都能被改写成无裁判的协议。多项式时间在这里是存在性粒度。它说明改写手续本身是高效的，不是一份按门数去装配产品的工时表。

诚实多数是安全谓词上的门槛，不是社交礼貌。设想少数玩家任意偏离：乱发消息、中途停止、把不该送的串送出去。只要其余人仍按协议走，并且人数过半，规定输出之外的部分信息仍须对多项式观察者隐藏。隐藏的口径是模拟：少数作弊者看见的整段对话，可以由一台不接触诚实输入的机器，只拿着规定输出与公共文本，生成出不可区分的替代文本。若替代文本已经够用，对话就没有多交出可计算的余量。这与戈德瓦塞尔–米卡利–拉科夫一九八五年论文里「自己能重造对话则没有得到额外知识」是同一套总体语言，对象从传证换成多人博弈。本页只使用这条总体语言，不把模拟改写成对线上系统的检测步骤。

零知识在编译器里只负责一件事：下一消息必须是说明书上的那一条。玩家先以密码学方式扣住自己的输入与硬币，使事后不能改口，却不必把内容摊开。每送出一条新消息，就附上一份计算零知识证明，证明这条消息等于下一消息函数在已扣住输入、硬币与公开文本上的值。验证者得到的是「计算正确」这一比特，不是手牌。一九八六年那条 $NP$ 零知识定理保证：只要该陈述在 $NP$ 里，模块就存在。库克一九七一年论文里那种一次性短证书，在这里恰好是高知识的反面教具——直接把证书写下来会把输入交出去；零知识把同一份 $NP$ 证据留在对话里，而不变成可读的牌面。强制诚实不是靠事后审计日志，而是靠「发得出去的消息必须可证」。存在性到此为止。本页不写轮次表，不写承诺方案的参数，也不写如何把一份证明改造成攻击。

硬币属于随机算法那一类资源，在这里却不是为了把期望运行时间压低。协议需要公共的不可预测比特，用来发出挑战、掩蔽承诺，并让模拟器有地方塞进自己的随机带。私有硬币仍归各人保管，因为它们是输入的一部分。把本页听成又一篇「用随机换时间」的算法综述，会把信任结构上的硬币收成渐近符号里的硬币。计算复杂性 提供的是多项式时钟与观察者类别；十二页把这两样钉在编译器与模拟器上，并不裁决 $P$ 对 $NP$。

编译代价对说明书规模是多项式，因此「任意博弈」是可执行的改写，不是口号。多项式可以很大，十二页并不给出实用轮数。这句话不是装配产品的步骤。

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

它证明了：存在多项式时间的编译器，把任意一局带不完备信息、人数不限的博弈说明书，改写成一套协议；若诚实玩家占多数，则任何多项式时间的观察者都不能从对话里抽出规定输出之外的部分信息。它把「需要公正裁判」从制度假设改写成可编译的对象，并把零知识从「整个 $NP$ 都能传证」降成「下一消息这一条 $NP$ 陈述必须可证」。函数与电路负责说明书能被计算，诚实多数负责少数偏离仍可被挡住，模拟负责把对话上的优势送回「没有多知道」。承诺串与证明文本在统计上远不是绝对静默，计算上却可以分不开。

它没有证明单向函数存在，也没有重证整个 $NP$ 都有零知识，更没有裁决 $P$ 对 $NP$。十二页是条件句：若零知识模块与底层单向或陷门对象在那儿，编译器就会跟着在那儿。它没有给出 1986 年那条图三着色或哈密顿回路上的零知识对话，也没有给出 1985 年二次非剩余上的无条件例子。它没有覆盖姚期智 1986 年那条两方混淆电路，没有把两人之局里的一人作弊收进诚实多数，也没有把后年那条私有信道上的完备性定理写成封面。它没有给出对已部署协议的区分步骤，也没有把「不泄露部分信息」写成一份选择输入攻击日程。限度还写在门槛上：诚实若不过半，这句定理不说话。对照属于 计算复杂性 地图与 密码学基础 总览。本页把编译器写成一次带诚实多数的条件句。

跨域连接

  • 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：那十四页把额外知识写成真实对话与模拟器文本的不可区分，对象是传证。本页把同一口径搬到多人博弈：少数作弊者看见的消息，必须能由规定输出重造。没有 1985 年的模拟器，1987 年少了「部分信息」的量词；没有本页的编译器，零知识仍停在证明对话。把两篇听成一次印刷，会把传证问题收成传牌面问题。
  • 交互式证明与零知识：总览页管公开硬币、多项式空间上界与后来的概率可验证明。本页只抽出零知识作为强制下一消息的螺丝。一九八六年那条「整个 $NP$ 都有计算零知识」在总览里是地图上的一格，在本页里是被调用的模块，不为它另立条目。把 1987 年听成又一次零知识完备性，会把博弈说明书从画面里擦掉。
  • 姚期智：1986 年 FOCS 的混淆电路把任意布尔电路编译成两方求值，门的真值表藏在密文里，诚实多数不是那条定理的门槛。本页的编译器面向任意人数，安全句子以多数诚实为条件，强制手段是零知识而不是加密真值表。把两份 1986–1987 的印刷听成一次「已经解决隐私计算」，会把两方电路与多方博弈焊成一句。
  • 姚期智一九八二年陷门函数论文：芝加哥那十二页把计算不可区分写成密码学与发生器共用的装置。本页继承「多项式测试者分不开」这一句，把测试者升级成参加博弈的少数作弊者，并加上诚实多数这一档门槛。没有不可区分语言，编译器交不出可陈述的安全；没有本页的说明书，陷门仍停在假硬币一侧。
  • 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把密文总体写成多项式不可区分，对象是传一条消息。本页把不可区分从密文搬到整段多人对话，货物从明文换成规定输出之外的一切。年份相邻，封面却分别是公钥编码与心智博弈。把 1987 年听成又一篇概率加密，会把下一消息收成一次密文抽样。
  • 戈德赖希–戈德瓦塞尔–米卡利一九八六年论文：那十六页把发生器铺成可询问的函数族，作者名单里同样有戈德赖希与米卡利，产品却是函数不是协议。本页不造函数。把两篇听成一次印刷，会把树与博弈叠成一句。
  • 密码学基础：总览需要单向函数、不可区分、零知识与安全计算。本页提供 1987 年把任意说明书焊成诚实多数协议的那一次：零知识负责下一消息像规定的那样，多数负责少数偏离仍可模拟，编译器负责全称量词落在多项式时间里。它没有把轮次写成步骤。
  • 库克一九七一年论文：书里的短证书是高知识的传证。下一消息的正确性恰好是这类陈述；直接写下来会把输入交出去。本页调用零知识，使同一陈述可被说服而不变成牌面。

参考文献

  1. 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. ISBN: 0-89791-221-7. Editor: Alfred V. Aho. —— 本文对象。
  2. 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, 1986, pp. 174–187. DOI: 10.1109/SFCS.1986.47. —— 一九八六年零知识完备性，本页的模块，不是封面。
  3. 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. —— 一九八六年定理的期刊全文，不是 1987 年编译器。
  4. 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. —— 零知识定义的先行文本，对象是传证。
  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. —— 两方混淆电路邻居，不是诚实多数编译器。
  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$ 陈述。

延伸阅读

正文中引用本条 · 3