沙菲·戈德瓦塞尔

破除误解：零知识不是把秘密再加密一遍#

把零知识听成「用更强的加密把证据藏起来」，会整段读错。加密的目标是传递内容，只是内容对旁观者不可读；零知识的目标是根本不传递内容。形式标准是模拟器：对任意多项式时间的验证者 $V^*$，存在一个不与证明者对话的算法 $S$，其输出与 $V^*$ 在真实对话里的视角不可区分。若验证者自己就能「梦见」整场对话，他就没有从证明者那里学到新东西。

第二个误解是把语义安全当成香农的完美保密。香农要求密文与明文的互信息严格为零，因而密钥至少与明文一样长。戈德瓦塞尔–米卡利退到计算不可区分：允许统计上有差别，但任何多项式对手都测不出来。这是现代 密码学基础 的认识论转向——安全是相对假设与相对算力的谓词，不是绝对静默。

第三个误解是把交互式证明当成「不严格的证明」。错误概率可经独立重复压到 $2^{-100}$ 以下，低于硬件故障。戈德瓦塞尔强调的是可靠性（soundness）对任意作弊证明者成立，而不是对某一种作弊手法成立。概率在这里不是偷懒，是让验证者提出证明者无法预知的问题。

现场：二次剩余如何加密一个比特#

戈德瓦塞尔–米卡利方案（会议版 1982，期刊版 1984）把语义安全做成本能看见的数论游戏。公钥是模数 $n = pq$ 和一个雅可比符号为 $1$ 的二次非剩余 $y$。加密比特 $b$：随机选 $x$，输出

$$c \equiv x^2 y^b \pmod{n}.$$

$b=0$ 时 $c$ 是二次剩余；$b=1$ 时 $c$ 落在雅可比符号为 $1$ 的非剩余那一半。解密者知道因子，能判定二次剩余性，因而能读出 $b$。对手若不能在不知道因子时区分这两类数——二次剩余假设——就不能区分 $0$ 和 $1$ 的密文。

关键设计有三处，缺一则语义安全垮掉。第一，加密必须随机：同一比特每次应得到不同密文，否则对手用重放就能做相等性测试。第二，必须按比特（或按块加随机填充）加密，因为确定性公钥算法无法满足「任意等长消息对不可区分」。第三，安全性被写成游戏：对手自选 $m_0,m_1$，挑战者抛硬币加密其中一个，对手猜硬币。优势必须可忽略。今天教材里的 IND-CPA，就是这场游戏的直系后裔。

加密基础 里的 RSA 教科书版本是确定性的模幂。戈德瓦塞尔的论点是：那种「算得出来就安全」的直觉不够。罗纳德·里维斯特 等人给出了可部署的陷门；戈德瓦塞尔–米卡利给出了必须满足的定义。工程上 RSA 后来叠 OAEP 一类填充，正是把语义安全补回确定性陷门上。定义先于补丁：没有 1982 年那场游戏，填充看起来只是实现细节。

GMR：把证明变成带硬币的对话#

1985 年 STOC 论文（期刊版 1989 年刊于 SIAM Journal on Computing）给出交互式证明的三条公理，对象见 GMR 1985。证明者计算力不限，验证者只许多项式时间并可以抛硬币。完备性：命题为真时，诚实证明者让验证者以高概率接受。可靠性：命题为假时，任何证明者都无法以不可忽略的概率让验证者接受。零知识：真实对话可被模拟器伪造。

图不同构是早期名例。要证明 $G_0$ 与 $G_1$ 不同构，验证者私下随机选一张图、随机重排顶点，问「这来自哪一张？」若两图确实不同构，无限强的证明者总能答对；若同构，重排后的图与两者都无法区分，证明者只能猜。每轮声音度为 $1/2$，重复后指数下降。零知识来自：验证者看见的，只是自己已经能生成的随机同构图——模拟器可以自己选答案再生成那张图。

「知识复杂度」是标题里的第三个词：一场证明泄露了多少比特的知识。零知识是泄露为零（计算意义下）的极端。这个量后来在证据不可区分、模拟抽取器、知识证明（proof of knowledge）里分化。戈德瓦塞尔坚持用模拟而不是「看起来没说秘密」来定义，是因为后者无法被数学否证——你会永远觉得自己没看见，直到有人写出从对话里抽出陷阱门的算法。

戈德瓦塞尔与西普瑟（Sipser）1986 年证明，私有硬币与公开硬币的交互式证明能力本质相同：验证者不必把硬币藏起来也能达到同样的语言类。巴巴伊的亚瑟–梅林协议要求硬币公开；GMR 允许私藏。能力重合说明，模型的力量来自交互与随机，而不是来自「藏骰子」这一戏剧性细节。日后 IP = PSPACE（沙米尔，在伦德、福特诺、卡洛夫、尼桑的算术化之上）用的是公开硬币技术，但它所验证的对象，首先要被 GMR 的对话定义承认是「证明」。

伪随机函数，以及定义如何变成构件#

1986 年，戈德赖希、戈德瓦塞尔与米卡利给出从伪随机发生器构造伪随机函数的 GGM 构造：把发生器看成二叉树的左右子，沿输入比特往下走，输出叶子。若发生器安全，则函数与真随机函数在多项式对手面前不可区分。这把「一块短种子」升级成「可评估的随机神谕」，成为私钥加密、消息认证和后续可证明安全协议的标准零件。

布卢姆–戈德瓦塞尔密码系统则把二次剩余与布卢姆–布卢姆–舒布发生器连起来，得到比逐比特 GM 更紧凑的方案。戈德瓦塞尔的论文目录里，反复出现同一手法：先写不可区分游戏，再给一个基于标准假设的构造，最后证明任何能赢游戏的对手都能打破假设。密码学基础 今天把这叫归约；1980 年代中期，它还不是默认文体。

知识证明把可靠性从「语言成员」加强为「证明者必须知道证据」。抽取器能从任何让验证者接受的策略里抽出那份证据。身份认证依赖这一层：你要证明知道私钥，而不是仅仅证明「存在一把私钥对应这个公钥」——公钥已经公开时，后一句话是空洞的。戈德瓦塞尔参与塑造的模拟与抽取语言，后来成为 Sigma 协议与 Fiat–Shamir 启发式的阅读框架：先有交互的知识证明，再把硬币换成哈希，试图得到非交互版本。启发式不是定理。随机神谕模型里可证，标准模型里要另付代价。把 zk-SNARK 写成 GMR 的直接推论，会跳过抽取器、电路可满足性、多项式承诺这三层。正确谱系是：GMR 给出零知识与交互验证的公理，后续工作把公理实例化到特定代数并删掉轮次。

她与米卡利的图灵奖引文同时点名复杂性理论：交互式证明不仅服务密码协议，也重画了 NP 之外的验证地图。IP = PSPACE、PCP 定理、简洁非交互零知识，都走在 GMR 打开的那条路上。把 2012 年的奖读成「发明了区块链上的 zk-SNARK」会时代错乱；正确的因果是：先有模拟器定义，才有后来把交互去掉、把证明长度压到常数的工程。

戈德赖希–戈德瓦塞尔–罗恩在 1990 年代把「随机抽查局部」写成性质测试：只需读输入的极小一部分，就能以高概率区分「对象满足某全局性质」与「对象离该性质很远」。这与 PCP 的「错误必须被摊开」是同一家族的直觉，只是测试的对象从证明串换成了图或函数。戈德瓦塞尔的论文习惯再次出现：先规定距离与查询预算，再证明任何超过距离的对象都会被随机局部检查撞见。定义仍然先于构造。

代价与争议#

定义的代价。 语义安全默认的是选择明文攻击。选择密文攻击、适应性打开、组合环境下的安全性，每一层都要重新写游戏。戈德瓦塞尔推动的风格——安全必须相对明确的对手类——也意味着「我们加密了」这句话永远不够。工业协议若只引用 GM 或 GMR 的名字而不核对游戏，就会把定义当成装饰。

零知识的实现鸿沟。 GMR 的图同构协议漂亮，但不直接给出 NP 完全问题的高效零知识。戈德赖希–米卡利–维格德森（GMW）后来证明，若存在单向函数，则 NP 中每个语言都有计算零知识证明。理论闭合之后，轮数、证明长度、代数结构仍要再压缩一个数量级，才会出现可上链的 SNARK。争议常被写成「理论无用」或「工程不严格」：其实是同一条定义被不同资源预算实例化。

优先权与共同体。 交互式证明同时出现在密码学（GMR）与复杂性（巴巴伊的 AM）两侧。公开硬币与私有硬币、知识复杂度与语言类，早期论文互相引用但问题意识不同。戈德瓦塞尔–米卡利的图灵奖晚于若干后续定理（IP = PSPACE 在 1990，PCP 在 1990 年代），评审看重的是把密码学改写成复杂性游戏这一奠基，而不是某条最大的包含定理。这与 里维斯特 2002 年获奖、迪菲–赫尔曼 2015 年获奖的时间差同类：落地与定义、概念与最大定理，在奖项日历上并不重合。

机构与身份。 戈德瓦塞尔在 MIT 与魏茨曼科学院两地任教，是少数同时深度嵌入美国与以色列密码共同体的人物。图灵奖女性得主名单到她为止仍然很短（艾伦 2006、利斯科夫 2008、戈德瓦塞尔 2012）。把这一点写成唯一故事会掩盖她真正被引用的原因：语义安全与零知识是定义，不是象征。她后来也把同一套定义风格带进机器学习隐私与证明系统的课程，使「先写游戏」成为两代研究生的默认文体，而不只是两篇 1980 年代论文的纪念。

语义安全还有一层对工程最狠的推论：确定性公钥加密不可能满足该定义。 对手自己就能加密 $m_0$ 与 $m_1$ 并与挑战密文做相等比较。RSA 教科书里的裸模幂因此不是语义安全的；填充、随机填充与混合加密不是美化，是定义逼出来的补丁。戈德瓦塞尔没有反对 RSA 的陷门，她反对的是把陷门误当成安全定义。这一反对意见最终写进了所有现代标准的密钥封装说明。

合同的主语因此从明文换成了对手的视图。你要保证的不是对象藏得好，而是对方眼睛里的那份记录，与一份不含秘密的模拟记录不可区分。证明者可以很强，验证者必须保持多项式：说服发生了，证据的副本却没有发生。后来几乎所有「我有资格但不交材料」的协议，都在执行这同一份不对等合同。

1988 年，本-奥尔、戈德瓦塞尔、基利安与维格德森把证明者拆成彼此隔离的多人，得到 MIP。隔离本身成为资源：验证者可以问不一致的问题，交叉核对。这不是把零知识再讲一遍，而是把「证明者是否共谋」写成模型参数。戈德瓦塞尔、米卡利与里维斯特把同一套合同用到数字签名：自适应选择消息攻击下的不可伪造。对手可以指定要签的消息，仍造不出新的有效签。签名安全从此不再是「没见过两份相同的签」，而是一条关于询问接口的游戏。

与隐私工程的交界也容易被说滑。零知识能让你证明资格而不交复印件，它并不自动回答数据该不该被收集。合同只管一次对话的知识增量，不管机构的激励。把零知识宣传成隐私的全部，是另一种违约。定义改变密码学合同之后，部署仍然要面对谁来举行仪式、随机数从哪来、侧信道会不会把游戏外的视图交出去。

跨域连接#

• 证明：GMR 把证明从一份可静态核对的文书改成一场带随机挑战的对话。可靠性不再是「证书格式正确」，而是「假命题上任何策略都骗不过硬币」。零知识又加上第三条：对话必须可被不拥有证据的模拟器生成。证明论因此多了一维——知识可以不随确信一起交付。
• 概率：语义安全与零知识都是不可区分陈述：两组随机实验的输出在多项式统计检验下重合。二次剩余加密的硬币来自均匀选 $x$；交互式证明的硬币来自验证者的挑战。失败概率必须对最坏作弊者取指数下降，而不是对平均作弊者取均值。概率在这里构造信任，而不是节省平均运行时间。
• 测度论：计算不可区分要求对所有多项式可测的事件，两边概率只差一个可忽略函数。可忽略是渐近陈述：比任何 $n^{-c}$ 都小。没有「对所有可测集」这一全称量词，对手就可以专挑一个泄漏事件；没有可忽略，多项式重复就会把差别放大成常数量级的优势。
• 信息哲学：零知识切断了「我确信 $P$」与「我拥有 $P$ 的证据」之间的日常等同。验证者的后验可以在命题真值上崩溃到近乎 1，而在证据的任何非平凡函数上与先验不可区分。知道与拥有被拆开：这不是修辞，是模拟器给出的可检验标准。
• 信息不对称：心智扑克、身份认证、公开验证的私有凭证，都要求一方证明自己守规且不交出私有输入。零知识把不对称设计进协议：证明者相对验证者拥有证据，验证者相对旁观者拥有确信，旁观者什么也得不到。市场若把「看过证明」当成「拿到了可转发的把柄」，就会把买票、胁迫与泄漏重新引进门。

人物小记：先写游戏，再写方案#

戈德瓦塞尔的论文读起来常像在立法：先规定对手允许做什么，再宣布何种优势算赢，最后才出现一次模幂或一次图同构。这种文体后来成为可证明安全的默认，却也让她的公众形象不如 RSA 三个字母响亮——没有以她姓氏缩写命名的默认网关算法。

若把贡献压成一句：她坚持安全必须是一场规则公开的游戏，而不是一份「目前没人破」的清单。 GM 的二次剩余方案今天很少直接部署；GMR 的图同构协议也不是 zk-SNARK 的线路图。活下来的是游戏本身。网关填充、零知识电路、证明系统的模拟抽取器，都还在回答 1982 年和 1985 年那两场 STOC 提问。窄定义让后来者可以接力，也可以把实现与假设分开骂。二次剩余加密可以被替换，GMR 签名可以被替换，零知识的具体交互轮数可以被压成非交互。不能替换的是那条主语：我们担保的是对手的视图，不是自己的感觉。

参考文献#

• Goldwasser, S. & Micali, S. *Probabilistic Encryption.* Journal of Computer and System Sciences 28(2), 1984.（会议版 STOC 1982）
• Goldwasser, S., Micali, S. & Rackoff, C. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing 18(1), 1989.（会议版 STOC 1985）
• Goldwasser, S. & Sipser, M. Private Coins versus Public Coins in Interactive Proof Systems. STOC, 1986.
• Goldreich, O., Goldwasser, S. & Micali, S. How to Construct Random Functions. Journal of the ACM 33(4), 1986.
• Goldreich, O., Goldwasser, S. & Ron, D. Property Testing and its Connection to Learning and Approximation. Journal of the ACM 45(4), 1998.
• Blum, M. & Goldwasser, S. An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information. CRYPTO, 1984.
• Goldreich, O., Micali, S. & Wigderson, A. Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. Journal of the ACM 38(3), 1991.
• Shamir, A. IP = PSPACE. Journal of the ACM 39(4), 1992.
• Goldwasser, S. & Micali, S. Turing Award Lecture. ACM A.M. Turing Award, 2012.
• Goldwasser, S., Micali, S. & Rivest, R. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM Journal on Computing 17(2), 1988.
• Ben-Or, M., Goldwasser, S., Kilian, J. & Wigderson, A. Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions. STOC, 1988.

延伸阅读#

• Goldreich, O. Foundations of Cryptography. Vol. 1, Cambridge University Press, 2001.（把语义安全、零知识与伪随机写成统一语言的标准专著）