Goldwasser–Micali 1984：语义安全怎样把密文写成多项式不可区分

破除误解：语义安全不是香农静默，概率加密也不是已经配好的公钥#

第一种最快的读法是：把戈德瓦塞尔–米卡利听成 1985 年那十四页，或听成 1982 年那十三页 STOC。三人与拉科夫合写的是传证问题：对话文本除了「命题为真」这一比特，还不得不交出多少额外知识。两人 1984 年合写的是传消息问题：密文除了合法收信人能唯一还原，还不得让多项式时间的旁观者多知道明文的任何可计算函数。会议先行本把心理扑克写进标题，期刊把定义、归约与二次剩余假设写完整。把三份封面收成一句，会把加密定义与零知识定义焊成一次页码。

第二层误解把语义安全听成香农 1949 年《保密系统的通信理论》里的完美保密：密文与明文的后验必须等于先验。香农的对手不限算力，因而密钥至少与明文一样长。本页明确写成多项式有界的香农口径：对手只有多项式规模的电路；拦截密文之后，关于明文的任何函数，凡是仍可高效算出来的，本来不看密文也能高效算出来。统计上两总体可以相距很远，计算上却分不开。把语义安全听成一次性密码本，会把一次复杂性陈述收成一次概率恒等式。本页讨论香农的保密定义，并不把那条信息论地图再印一遍。

第三层误解把多项式不可区分听成「密文看上去乱」，或听成一份选择明文攻击的操作手册。原文的多项式安全用线路窃听者与明文寻找器来写：前者是看见公开编码手续与密文的多项式电路，后者试图交出两个明文，使两段密文总体仍可被分开。公钥已经把编码手续放进公开文件，因此形成「自己选定字符串」的密文总体，在定义里本来就被许可。这是后来课堂称作选择明文攻击下不可区分的直觉来源，不是一份询问日程。选择密文那一档，原文第七节点名为另一种对手；那不是本页封面。

第四层误解把二次剩余听成已经证明困难，或听成可以搬进实验室的判定手续。三十页是条件句：若判定因子未知合数上的二次剩余性对多项式电路仍然困难，则这一枚陷门谓词不可逼近，概率加密因而多项式安全、因而语义安全。它没有证明分解困难，也没有证明二次剩余判定困难，更没有裁决 $P$ 对 $NP$。高斯 1801 年《算术研究》把二次剩余性列为公开的算法问题；本页把它收成电路规模上的不可行性假设，并证明这一族问题要么几乎处处难、要么几乎处处易。假设是硬度假说。

语义安全、多项式不可区分，以及作为硬度假说的二次剩余#

装置从「确定性陷门函数为什么不够」开始。迪菲与赫尔曼 1976 年把公钥写成正算容易、反算需要陷门的函数；里维斯特、沙米尔与阿德尔曼 1978 年的 RSA，以及拉宾 1979 年那份与分解一样难的公开函数，是原文点名的两枚具体陷门。戈德瓦塞尔与米卡利给出两层异议。第一，函数在泛用输入上难求逆，并不排除明文具有结构时求逆变容易。第二，难求整段原像，并不排除密文已经泄露了原像的某一谓词。心理扑克属于 1982 年先行本的动机：交换加密未能证明隐藏牌面的所有部分信息。期刊把这句话收成定义问题：加密必须对任意明文空间、任意先验分布，都让部分信息不可高效提取。

他们用来替换陷门函数的，是不可逼近的陷门谓词。任何人都可以抽样出使谓词为真或为假的实例；只有握有陷门的人，看见实例之后才能判定谓词。没有陷门时，多项式资源的对手猜这一比特，不该比抛硬币好上不可忽略的一点。编码手续因此必须抛硬币：同一明文对应许多密文，合法收信人仍能唯一还原。明文按比特送入，每一位各自对应谓词的一次抽样。这是模型语言，不是一份把随机数焊进模运算的装配说明。确定性的公开编码做不到这一点：候选明文一旦短得可以枚举，公开手续本身就会把「是不是这一条」变成可核对的谓词。

多项式安全把「密文总体必须分不开」写成电路。消息生成器给出任意分布上的明文空间。若仍存在多项式规模的寻找器，能交出两个明文，使多项式窃听电路对两段密文总体的输出频率出现不可忽略的缝，系统就还不是多项式安全。定理 5.1 证明：凡是建立在不可逼近陷门谓词上的概率公钥系统，都是多项式安全的。归约把两个可区分的明文沿最短翻转路径收到相邻一对，再把只差一比特的那条缝送回陷门谓词。

语义安全把同一件事写成「看了密文也不该多算得出函数值」。函数不必可计算，甚至不必递归。不看密文时，最好的多项式策略就是猜先验上最常见的函数值。看了密文之后，若某台多项式电路仍能以不可忽略的优势猜得更好，系统就还不是语义安全。定理 5.2 证明多项式安全蕴含语义安全。公钥环境下，编码手续公开，选择明文那一档的直觉已经含在装置里；对手事先知道明文分布，正是定义所针对的、最不利的先验。后年教材把这场游戏叫做选择明文攻击下的不可区分，是这条定义的直系后裔，不是攻击菜谱。

第一次实现把不可逼近的陷门谓词取成二次剩余性。合数的因子未知时，给定雅可比符号为加一的整数，判定它是不是模这个合数的平方，被写成二次剩余问题。因子已知则判定落在多项式时间里，这是陷门；雅可比符号本身即使不知道因子也能多项式算出，等于减一则必为非剩余，等于加一时才进入困难的一半。二次剩余假设把这句话收成电路下界：对所谓难合数族，能在不可忽略比例的模数上判定剩余性的电路，规模必须超过一切多项式。高斯把这个问题与素性、分解并列为算术的公开问题。假设停在这里。本页不讨论如何选取模数、如何计算符号、如何把判定改写成分解手续。

第六节的数论结果表明，这一族问题的平均情形与最坏情形靠得很近。若某台电路只在不可忽略比例的实例上答对剩余性，随机化就能把这一点优势摊到几乎所有实例上。他们还证明，公开一枚随机抽取的二次非剩余，并不会让判定突然变容易。于是二次剩余谓词在该假设之下是不可逼近的陷门谓词。布卢姆与米卡利给出的离散对数左右半不带陷门；本页需要陷门，因为合法收信人必须能还原。姚期智证明一对一陷门函数足以造出这类谓词，那是存在性邻居。戈德赖希与列文 1989 年才给出任意单向函数上的内积硬核；本页提供的是数论上的指定比特。

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

它证明了：公钥加密的安全可以写成多项式时间观察者面前的谓词，而不必写成香农式的统计静默。它给出语义安全与多项式安全两套定义，并证明后者蕴含前者；建立在不可逼近陷门谓词上的概率公钥系统因此对任意明文空间、任意先验分布都语义安全。它引入二次剩余假设，证明这一判定要么几乎处处难、要么几乎处处易，并证明公开一枚随机非剩余不会改变硬度。于是因子未知合数上的二次剩余性成为第一枚被写成不可逼近陷门谓词的数论对象。安全性必须对所有部分信息、所有消息分布成立。这句话不是操作单。

它没有证明二次剩余判定困难，也没有证明分解困难，更没有裁决 $P$ 对 $NP$。三十页是条件句：若这种数论对象在那儿，语义安全就会跟着在那儿。它没有覆盖交互证明与零知识——那是 1985 年把不可区分从密文搬到对话文本的邻居。它没有给出布卢姆–米卡利那种自身落在多项式时间里的发生器，也没有给出戈德赖希–列文那种对任意单向函数都成立的内积硬核。它没有处理选择密文攻击：原文承认窃听不是唯一的对手，并把通信中的主动对手留给另一篇 FOCS。它没有从任意单向函数构造加密，姚期智的存在性陈述仍要求一对一的陷门。

明文按比特送入，每一位对应模数那么长的一段密文，膨胀因子大约是模数的比特长度。三十页把安全写成对任意分布都成立的谓词，付出的是密文相对明文按比特拉长。后来更紧凑的方案属于邻居，不是页码 270 至 299。电路作为对手模型，是为了让公开文件公布之后再选窃听手续仍然合法。对照属于 计算复杂性 地图与 密码学基础 总览。膨胀回答的是这句定义在第一次实现里有多贵。这句话不是课堂密码实验。

跨域连接#

• 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：那十四页把不可区分从密文总体搬到证明对话的文本上，模拟器能造出的东西就不算额外知识。本页提供被搬动的那一套总体语言。作者重叠、假设里都出现二次剩余性，对象却分别是传消息与传证。把零知识听成本页的别名，会把 1985 年的知识度量收成 1984 年的加密游戏。
• 姚期智一九八二年陷门函数论文：芝加哥 FOCS 那十二页把计算不可区分写成密码学与发生器共用的装置，并证明一对一陷门函数足以给出不可逼近的陷门谓词。本页把谓词钉在二次剩余上，并把不可区分写成密文总体的安全口径。把两篇听成一次印刷，会把抽象放大与概率编码叠成一句。
• 布卢姆–米卡利一九八四年论文：同年 SIAM 那十五页给出不带陷门的不可逼近谓词，燃料是离散对数，产品是假硬币。本页需要陷门，因为收信人必须还原明文；产品是密文总体，不是比特源。把 1984 年听成同一篇，会把发生器与加密焊成一次页码。
• 密码学基础：总览需要单向函数、陷门与计算不可区分。本页提供 1984 年把三块焊在公钥加密上的那一次：陷门谓词负责合法还原，抛硬币负责同一明文对应许多密文，语义安全负责「看见密文不等于得到明文的任何可计算函数」。它没有把模数写成步骤。
• 交互式证明与零知识：总览页管公开硬币、多项式空间上界与后来的概率可验证明。本页停在加密定义。总览里的模拟器语言，沿用的正是这里的不可区分；没有 1984 年的密文游戏，1985 年少了一句「分不开就不算知道」的先例。
• 平均情况复杂性：五个世界问随机实例是否仍然难。二次剩余的自归约让这一族判定的平均情形与最坏情形靠得更近，本页把这份平均情形硬度集中到一枚陷门谓词上，再拉成对任意明文分布都成立的语义安全。它不把难实例的抽样写成攻击步骤。
• 随机算法：总览管蒙特卡洛误差如何被独立重复压下去。本页的硬币不是为了把错误界压低，而是为了让密文总体在多项式观察者面前叠在一起。归约内部的随机化是证明策略，不是把编码手续焊进素性检测的轮数表。

参考文献#

• 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. —— 本文对象。
• Shafi Goldwasser & Silvio Micali, "Probabilistic encryption & how to play mental poker keeping secret all partial information", Proceedings of the 14th Annual ACM Symposium on Theory of Computing, San Francisco, May 1982, pp. 365–377. DOI: 10.1145/800070.802212. —— 会议前身，不是本页封面。
• Claude E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal 28(4), 1949, pp. 656–715. DOI: 10.1002/j.1538-7305.1949.tb00928.x. —— 完美保密的先行文本。
• Whitfield Diffie & Martin E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory 22(6), 1976, pp. 644–654. DOI: 10.1109/TIT.1976.1055638. —— 公钥与陷门函数模型的先行文本。
• R. L. Rivest, A. Shamir & L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21(2), 1978, pp. 120–126. DOI: 10.1145/359340.359342. —— 原文点名的确定性陷门邻居。
• Michael O. Rabin, "Digitalized Signatures and Public-Key Functions as Intractable as Factorization", MIT/LCS/TR-212, 1979. —— 原文点名的另一枚陷门邻居。
• 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. —— 不可区分语言与陷门谓词的存在性邻居。
• Manuel Blum & Silvio Micali, "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits", SIAM Journal on Computing 13(4), November 1984, pp. 850–864. DOI: 10.1137/0213053. —— 同年邻居：不带陷门的不可逼近谓词。
• Shafi Goldwasser, Silvio Micali & Charles Rackoff, "The Knowledge Complexity of Interactive Proof-Systems", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 291–304. DOI: 10.1145/22145.22178. —— 把不可区分从密文搬到证明对话。
• Oded Goldreich & Leonid A. Levin, "A Hard-Core Predicate for all One-Way Functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 25–32. DOI: 10.1145/73007.73010. —— 后年邻居：任意单向函数上的内积硬核。
• C. F. Gauss, Disquisitiones Arithmeticae, 1801; English translation by Arthur A. Clarke, Yale University Press, 1966. —— 原文把二次剩余性追溯到高斯列出的算术公开问题。

延伸阅读#

• 与 戈德瓦塞尔–米卡利–拉科夫一九八五年论文 对读：密文上的不可区分对对话文本上的不可区分。
• 与 布卢姆–米卡利一九八四年论文 对读：假硬币对语义安全，不带陷门对带陷门。
• 与 密码学基础 对读：语义安全是定义，不是一份已造好的公钥。