Naor–Yung 1990：被动窃听上的公钥怎样加上非交互零知识挡住选择密文

破除误解：选择密文不是一份攻击手册，午餐时间也不等于后年那一档#

第一种最快的读法是：把纳奥尔–扬听成 1989 年那十一页通用单向哈希，或听成同年 CRYPTO 的 LNCS 第 537 卷，或听成 1984 年那三十页概率加密。两人 1989 年合写的是哈希；两人 1990 年合写的是更强对手类上的公钥存在性。戈德瓦塞尔与米卡利写的是被动窃听。会议录写在封面上：巴尔的摩、五月、ACM，不是圣芭芭拉、八月、斯普林格。

第二层误解把「选择密文」听成一份询问解密手续的操作日程，或听成教人去拼装恶意密文的步骤。原文把对手类写成比被动窃听更强的一种资源：在见到自己要区分的那条挑战密文之前，对手可以对解密手续拥有访问权；见到之后，访问被收回。后来课堂把它叫做午餐时间攻击，或 CCA1。名字里的「午餐」是时间窗的比喻，不是场景说明书。定义回答的是「安全口径相对哪一种资源成立」，不回答「怎样去使用那一种资源」。本页停在对手类，不把访问权展开成询问次序，更不把归约里的模拟写成对部署系统的检测步骤。

第三层误解把十一页听成已经挡住自适应选择密文，或听成已经给出不可延展性。拉科夫与西蒙 1991 年才把时间窗拉到见到挑战之后：那一档后来被叫做 CCA2，十一页没有覆盖。多列夫、德沃克与纳奥尔把另一句话写成定义：看见一条密文，不该能造出明文与之相关的另一条密文。不可延展性不是本页封面，作者名单里虽然再次出现纳奥尔，对象却是相关性而不是午餐时间的区分游戏。克拉默与肖普 1998 年给出不必再调用非交互零知识、在标准数论假说下可具体分析的方案，那是八年后的工程邻居，不是页码 427 至 437。把后年三句话提前写进 1990 年，会把一次存在性条件句收成一部选择密文史。

第四层误解把二次剩余听成已经证明困难，或把双密文加证明听成可以搬进实验室的编码手续。十一页是条件句：若存在挡住被动窃听的公钥系统，并且共享随机串模型里存在对「两段密文藏同一明文」这一语言的非交互零知识，则存在挡住午餐时间这一档的公钥系统。二次剩余同时给了戈德瓦塞尔–米卡利那一档被动安全，也给了布卢姆–费尔德曼–米卡利那一档共享串上的非交互证明，因而成为被点名的燃料。它没有证明分解困难，也没有证明二次剩余判定困难，更没有裁决 $P$ 对 $NP$。共享随机串是一段公开的均匀随机对象，不是密钥，也不是后年用哈希函数把交互压成单条消息的启发式。假设是硬度假说。

双密文、同文证明，以及共享随机串上的非交互零知识#

装置从被动窃听不够用开始。迪菲与赫尔曼 1976 年把公钥写成正算容易、反算需要陷门的公开程序；默克尔 1978 年把公开分发的窃听代价抬成平方。戈德瓦塞尔与米卡利把被动观察者面前的安全写成语义安全与多项式不可区分。公钥已经把编码手续放进公开文件，因此「自己选定明文、看见对应密文」这一档直觉，在被动定义里本来就被许可。十一页点名的缺口是另一档：对手若在见到挑战之前还对解密手续拥有访问权，密文总体还能否保持不可区分。缺口是定义上的，不是一份使用解密手续的教程。

他们用来填缺口的形状，是两次独立编码加上一段非交互证明。合法密文看起来像一对底层密文，外加一份「这两段藏着同一明文」的证明。共享随机串事先对编码者与核验者都可见，串本身公开。核验者只检查证明是否相对于这对密文与共享串成立；合法收信人在证明被接受之后，才用自己的陷门还原其中一段。形状存在，是为了让归约说得出口：两把独立的公钥可以被拆开，归约可以掌握其中一把的陷门，用来承接挑战之前那一档访问权；挑战的另一半仍然是底层被动安全系统的新鲜密文。证明若可靠，明文不一致的对子不会被当成合法密文。证明若是零知识，看见证明不等于多知道明文的可计算函数。这是存在性归约的架构语言，不是把随机数焊进模运算的装配说明，更不是一份把字符串送进解密手续的日程。

非交互把 1985 年那一套对话语言收成单条附属消息。戈德瓦塞尔–米卡利–拉科夫把零知识写成：多项式时间的听者自己就能生成与真实对话不可区分的文本。布卢姆、保罗·费尔德曼（Paul Feldman）与米卡利在 1988 年第二十届 STOC 把交互拿掉，改成共享随机串模型：证明者与验证者共同看见一段事先抽样的公开随机串，证明是串上的一条消息，不必再来回问答。本页需要的正是这一模型。被证明的语言是「两段密文是同一明文的合法编码」，它落在 $NP$ 里，因为短证书可以是两段编码自己的随机带。共享串不是秘密，任何人都可以核验；它也不是把对话哈希掉的后年启发式。没有共享串，非交互零知识在标准模型里当时还站不稳。本页把串当成公共参数，不把抽样手续写成密钥编制。

第一次被点名的燃料是二次剩余。因子未知的合数上，判定雅可比符号为加一的整数是不是平方，被戈德瓦塞尔与米卡利写成带陷门的不可逼近谓词，并据此交出被动安全的概率公钥。同一数论对象也支撑共享串上的非交互证明。于是条件句可以落在一处：若二次剩余判定对多项式电路仍然困难，则被动安全与非交互零知识都在那儿，午餐时间这一档也就跟着在那儿。姚期智 1982 年已经把计算不可区分写成密码学共用的装置；本页把不可区分的对象从「只看见密文」升级成「在挑战之前还对解密手续拥有访问权」。升级发生在对手类上，不发生在模数的选取步骤上。本页不讨论如何选取合数、如何计算符号、如何把判定改写成分解手续。

戈德赖希–戈德瓦塞尔–米卡利 1986 年把发生器铺成可询问的函数族。那十六页的神谕是函数值，不是解密手续。硬币在本页里出现两次：底层概率加密需要硬币，才让同一明文对应许多密文；非交互证明也需要硬币，才让模拟器造得出附属消息。随机算法总览里的硬币常常为了把错误界压低；这里的硬币为了让总体叠在一起。归约内部的随机化是证明策略，不是编码轮数表。

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

它证明了：公钥加密的安全口径可以相对比被动窃听更强的对手类来写。若存在挡住被动窃听的公钥系统，并且共享随机串模型里存在对「同文对」的非交互零知识，则存在挡住午餐时间这一档——后来课堂称作 CCA1——的公钥系统。它给出一种存在性形状：两次独立编码，外加一段同文证明；归约靠拆开两把公钥来回答挑战之前的访问权，靠零知识与可靠性把证明从明文信息里剥开。它把二次剩余写成足够点燃整条条件句的燃料。安全性必须在该对手类面前仍对密文总体的不可区分成立。这句话不是操作单。

它没有证明二次剩余判定困难，也没有证明分解困难，更没有裁决 $P$ 对 $NP$。十一页是条件句：若这种数论对象与这种非交互证明在那儿，午餐时间这一档就会跟着在那儿。它没有覆盖自适应选择密文：拉科夫与西蒙 1991 年才把时间窗拉到见到挑战之后，那一档后来被叫做 CCA2。它没有覆盖不可延展性：多列夫、德沃克与纳奥尔问的是密文被改写之后明文关系会不会泄漏。它没有给出克拉默–肖普那种不必再挂非交互零知识的具体方案，也没有从任意单向函数构造加密，更没有把 RSA 的模幂写成产品规格。

合法密文至少包含两段底层密文和一段证明，膨胀相对被动安全的第一次实现又拉长一截。共享随机串必须事先存在，并且对编码者与核验者都公开。对照属于 计算复杂性 地图与 密码学基础 总览。膨胀与共享串回答的是这句定义有多贵。这句话不是课堂密码实验。

跨域连接#

• 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把被动窃听下的密文总体写成多项式不可区分，燃料是二次剩余。本页假定那一档已经在那儿，再把对手类升级成挑战之前对解密手续拥有访问权。把 1990 年听成又一篇语义安全，会把午餐时间收成一次被动抽样。
• 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：那十四页把不可区分从密文搬到证明对话的文本上。本页需要后来被收成非交互、挂在共享随机串上的那一支：证明变成密文的附属物。把零知识听成本页的别名，会把传证问题收成加密游戏。
• 交互式证明与零知识：总览页管公开硬币、多项式空间与后来的简洁非交互证明。本页停在加密定义里对非交互零知识的一次调用。没有共享串模型里「同文对」可证，双密文形状就少了可核验的附属消息。
• 密码学基础：总览需要语义安全与更强的对手类。本页提供 1990 年把两块焊在一起的那一次：被动安全负责只看见密文时分不开，非交互零知识负责附加访问权时仍然分不开。它没有把模数写成步骤。
• RSA 公钥密码：算法页管模幂与填充。本页明确不是那份产品规格。确定性陷门在 1984 年已被指出不够语义安全；十一页更没有把模幂加上证明当成可部署系统。把封面听成 RSA 的安全补丁，会把存在性归约收成工程修订。
• 加密基础：概念页把对称、公钥与哈希收成入门地图。本页只抽出选择密文这一档在 1990 年怎样第一次被写成可归约的定义。地图上后来出现的自适应与混合加密，都不在页码 427 至 437。
• 姚期智一九八二年陷门函数论文：芝加哥那十二页把计算不可区分写成共用装置。本页把测试者的资源从「看见密文」改写成「挑战之前还对解密手续拥有访问权」。谓词没变，对手类变了。
• 迪菲–赫尔曼一九七六年论文：斯坦福那十一页把公钥写成公开程序。本页继承编码手续本来就公开，因此选择明文那一档的直觉已在被动定义里；要另写的是选择密文这一档。把 1976 年听成已经挡住午餐时间，会把陷门的存在性收成一次对手类定理。

参考文献#

• Moni Naor & Moti Yung, "Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks", Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, May 1990, pp. 427–437. DOI: 10.1145/100216.100273. ISBN: 0-89791-361-2. —— 本文对象。
• Moni Naor & Moti Yung, "Universal One-Way Hash Functions and their Cryptographic Applications", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, May 1989, pp. 33–43. DOI: 10.1145/73007.73011. —— 前一年同作者的哈希论文，不是本页封面。
• Advances in Cryptology — CRYPTO '90, LNCS 537, Springer, 1991. —— 同年密码学年会会议录，不是巴尔的摩 STOC。
• 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 & 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. —— 零知识的对话先行文本。
• Manuel Blum, Paul Feldman & Silvio Micali, "Non-Interactive Zero-Knowledge and Its Applications", Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 103–112. DOI: 10.1145/62212.62222. —— 共享随机串模型里的非交互零知识。
• 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. —— 公钥与陷门函数模型的先行文本。
• 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. —— 计算不可区分语言的先行文本。
• Ralph C. Merkle, "Secure Communications Over Insecure Channels", Communications of the ACM 21(4), April 1978, pp. 294–299. DOI: 10.1145/359460.359473. —— 公开信道上被动分发的先行邻居。
• 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. —— 可询问函数族的邻居，神谕不是解密手续。
• Charles Rackoff & Daniel R. Simon, "Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack", Advances in Cryptology — CRYPTO '91, LNCS 576, Springer, 1992, pp. 433–444. DOI: 10.1007/3-540-46766-1_35. —— 后年邻居：自适应选择密文，不是本页封面。
• Danny Dolev, Cynthia Dwork & Moni Naor, "Non-Malleable Cryptography", Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 542–552. DOI: 10.1145/103418.103474. —— 后年邻居：不可延展性，不是本页封面。
• Ronald Cramer & Victor Shoup, "A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack", Advances in Cryptology — CRYPTO '98, LNCS 1462, Springer, 1998, pp. 13–25. DOI: 10.1007/BFb0055717. —— 后年邻居：不必再挂非交互零知识的具体方案。

延伸阅读#

• 与 戈德瓦塞尔–米卡利一九八四年论文 对读：被动窃听下的语义安全对午餐时间这一档。
• 与 戈德瓦塞尔–米卡利–拉科夫一九八五年论文 对读：对话上的零知识对共享串上的非交互附属证明。
• 与 密码学基础 对读：选择密文是对手类上的定义，不是一份已造好的公钥，也不是自适应那一档的后年教材。