Dolev–Dwork–Naor 1991：看见密文之后为什么仍不该能改出相关明文的另一条

破除误解：看见密文仍不该能改出相关明文，这不是一份攻击手册#

第一种最快的读法是：把多列夫–德沃克–纳奥尔听成纳奥尔–扬 1990 年那十一页，或听成同年八月拉科夫–西蒙的自适应选择密文，或听成 1984 年那三十页概率加密。纳奥尔与扬写的是午餐时间的区分游戏。拉科夫与西蒙写的是见到挑战之后仍可访问解密的时间窗。戈德瓦塞尔与米卡利写的是被动窃听。会议录写在封面上：新奥尔良、五月、ACM，不是巴尔的摩、不是圣芭芭拉、不是斯普林格 LNCS。把「一九九〇到一九九一那三篇更强口径」收成一句，会把午餐时间、自适应与不可延展焊成一次页码。

第二层误解把「不可延展」听成一份教人去改写密文的操作日程，或听成密封拍卖里怎样把别人的报价改成更高一档的步骤。原文把性质写成一种否定：给定一条密文，多项式对手不该能交出另一条不同密文，使得两条明文落在事先指定的关系里。密封投标和透明中介是用来说明「为什么光挡住读出明文还不够」的场面，不是配方。定义回答的是「安全口径相对哪一种资源成立」，不回答「怎样去使用那一种资源」。本页停在相关性，不把场面展开成投标次序，更不把归约里的模拟写成对部署系统的检测步骤。

第三层误解把不可延展听成选择密文的第三档时间窗，或听成午餐时间与自适应的别名。纳奥尔–扬问的是：见到挑战之前，对解密手续的访问权会不会让密文总体可区分。拉科夫与西蒙把同一扇窗拉到见到之后。两档都是区分游戏，切点在挑战时刻的哪一侧。本页问的是另一句话：不必先读出明文，是否仍能造出明文与之相关的另一条合法对象。后年课堂有时把某一种不可延展口径与自适应选择密文收得很近。那是后话。一九九一年五月印在封面上的，是相关性，不是时间窗。

第四层误解把十一页听成已经给出克拉默–肖普那种具体数论方案，或听成必须有一个可信中心替所有人发钥匙。十一页是条件句：若被动安全与合适的非交互证明在那儿，不可延展的加密、承诺与知识证明就可以写成存在性对象。燃料被点名到陷门置换。它没有证明某一种具体数论谓词困难，也没有裁决 $P$ 对 $NP$。它明确不把可信中心写成装置的一部分。假设是硬度假说。

明文相关、时间窗，以及承诺与知识证明上的同一种形状#

装置从语义安全不够用开始。迪菲与赫尔曼 1976 年把公钥写成正算容易、反算需要陷门的公开程序。戈德瓦塞尔与米卡利把被动观察者面前的安全写成语义安全与多项式不可区分：看见密文，不该能算出明文的任何可计算函数。十一页点名的缺口是另一档：对手也许并不想读出明文，只想交出另一条合法密文，让对应明文与原来那一条落在某个关系里。缺口是定义上的，不是一份改写密文的教程。

密封投标是被点名的场面，不是步骤表。假设报价被编码成密文送进箱子。语义安全可以说：旁观的多项式对手不该从密文里读出那个数字。它没有说：同一个对手不该另交一条密文，使得打开之后的数字与原来那个数字相关——比如系统地高一档。透明中介是第二场：信件必须经过某个看得见密文、却不该被允许替换成相关密文的中间人。两场都用来说明「读不出来」与「改不成相关对象」不是同一句话。本页把场面停在动机，不把箱子里的手续写成投标指南，也不把中介写成攻击位置。

同一形状被写到另外两处。字符串承诺里，看见对某串的承诺，不该能另交一份承诺，使得打开之后的串与原来那一串相关。知识证明里，看见一份「我拥有短证书」的证明，不该能另交一份可接受的证明，使得被证明的证书与原来那一份相关。戈德瓦塞尔–米卡利–拉科夫把零知识写成：多项式时间的听者自己就能生成与真实对话不可区分的文本。知识证明还要求短证书对抽取器可及。库克 1971 年已经把「存在短证书、多项式时间可核验」写成完全性的语言。本页需要的不是判定 SAT，而是：证明被改写之后，相关性会不会跟着泄漏。三种对象共用一句话。不是三种攻击手册。

纳奥尔与扬 1990 年和拉科夫与西蒙 1991 年问的是区分游戏里解密访问权的时间窗。本页问的是关系。谓词从「这两条总体能不能分开」换成「能不能交出明文相关的另一条合法对象」。姚期智 1982 年已经把计算不可区分写成密码学共用的装置，也把陷门函数写成公钥的燃料。本页把测试者的任务从「区分」改写成「延展」。陷门置换被点名为足够点燃条件句的燃料。升级发生在要挡住的能力上，不发生在模数的选取步骤上。随机算法总览里的硬币常常为了把错误界压低；这里的硬币为了让密文总体叠在一起，并给模拟器一条随机带。归约内部的随机化是证明策略，不是编码轮数表。

非交互把 1985 年那一套对话语言收成单条附属消息。布卢姆、保罗·费尔德曼（Paul Feldman）与米卡利在 1988 年第二十届 STOC 把交互拿掉，改成共享随机串模型。戈德赖希、米卡利与维格德森 1986 年在 FOCS 证明：在合适的密码学假设下，每个 $NP$ 语言都有计算零知识。本页站在同一条传证链的下游，把「不可延展」写成可归约的定义，再焊回加密、承诺与知识证明。它没有重证整个 $NP$ 都有零知识。共享串是公共参数，不是密钥，也不是坐在中间的可信中心。

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

它证明了：公钥加密的安全口径可以相对「看见密文之后仍能造出明文相关的另一条密文」这一档能力来写。若存在挡住被动窃听的公钥系统，并且共享随机串模型里存在合适的非交互证明，则存在不可延展的公钥加密。同一句话对字符串承诺和知识证明也成立。它给出一种存在性形状，不依赖另设一个可信中心。它把语义安全写成已经不够用的前一档，而不是写成错误。安全性必须在该能力面前仍对相关性成立。这句话不是操作单。

它没有证明某一种具体数论谓词困难，也没有证明分解困难，更没有裁决 $P$ 对 $NP$。十一页是条件句：若被动安全、陷门置换与非交互证明在那儿，不可延展就会跟着在那儿。它没有覆盖午餐时间的第一次存在性：那是纳奥尔–扬 1990 年的封面。它没有覆盖自适应选择密文的时间窗：那是拉科夫–西蒙 1991 年八月的封面。它没有给出克拉默–肖普那种不必再挂非交互零知识的具体方案，也没有从任意单向函数构造加密，更没有把 RSA 的模幂写成产品规格。不可延展与 IND-CCA2 后来在课堂上被收得很近，那是后年的等价与翻译，不是页码 542 至 552 里已经印好的符号。

合法对象往往比被动安全的第一次实现更长，因为要挡住的是延展而不是只挡住区分。共享随机串必须事先存在，并且对编码者与核验者都公开。对照属于 计算复杂性 地图与 密码学基础 总览。膨胀与共享串回答的是这句定义有多贵。这句话不是课堂密码实验。

跨域连接#

• 纳奥尔–扬一九九〇年论文：那十一页把选择密文写成午餐时间，访问权停在见到挑战之前，问的是密文总体还能否保持不可区分。本页问的是看见密文之后能否交出明文相关的另一条合法对象。把两篇听成同一档，会把区分游戏的时间窗收成一次相关性。
• 拉科夫–西蒙一九九一年论文：那十二页把时间窗拉到见到挑战之后，附属证明必须可抽取。本页与它同年，封面却是新奥尔良而不是圣芭芭拉。相关性不是第三档时间窗。把五月与八月焊在一起，会把两种对象收成一次印刷。
• 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把被动窃听下的密文总体写成多项式不可区分。本页假定那一档已经在那儿，再问只挡住「读出明文」够不够。把 1991 年听成又一篇语义安全，会把不可延展收成一次被动抽样。
• 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：那十四页把不可区分从密文搬到证明对话的文本上。本页把同一套语言用到知识证明被改写之后会不会泄漏相关性。把零知识听成本页的别名，会把传证问题收成延展口径。
• 辛西娅·德沃克：人物页管差分隐私、格密码与算法公平。本页只抽出她与多列夫、纳奥尔在阿尔马登合写的这一枚钉子。把十一页听成人物评传，会把不可延展收成一条生平。
• 密码学基础：总览需要语义安全、午餐时间、自适应与不可延展几档口径。本页提供 1991 年把相关性写成可归约定义的那一次。它没有把模数写成步骤，也没有把投标场面写成操作单。
• 交互式证明与零知识：总览页管公开硬币、多项式空间与后来的简洁非交互证明。本页停在「知识证明被改写之后相关性会不会泄漏」这一句话。没有短证书可抽取，延展在证明对象上就写不下去。
• 姚期智一九八二年陷门函数论文：芝加哥那十二页把计算不可区分写成共用装置，也把陷门函数写成公钥燃料。本页把测试者的任务从「区分」改写成「延展」。谓词没变，要挡住的能力变了。

参考文献#

• Danny Dolev, Cynthia Dwork & Moni Naor, "Non-Malleable Cryptography", Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, May 1991, pp. 542–552. DOI: 10.1145/103418.103474. ISBN: 0-89791-397-3. —— 本文对象。会议录版权页常印一九九一年一月；开会地点仍是新奥尔良。若干目录把同一页码写成 10.1145/103418.103501，那是条目漂移，不是第二份封面。
• Danny Dolev, Cynthia Dwork & Moni Naor, "Nonmalleable Cryptography", SIAM Journal on Computing 30(2), 2000, pp. 391–437. DOI: 10.1137/S0097539795291562. —— 同一组定理后来补全的期刊长文，不是第二份封面。
• 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. —— 前一年邻居：午餐时间 / CCA1，不是本页封面。
• 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. —— 同年邻居：自适应选择密文的时间窗，不是本页封面。
• 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. —— 共享随机串模型里的非交互零知识。
• 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. —— 整个 $NP$ 的计算零知识，不是本页封面。
• 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. —— 计算不可区分与陷门函数语言的先行文本。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 短证书与多项式核验的先行文本。
• 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. —— 后年邻居：不必再挂非交互零知识的具体方案。

延伸阅读#

• 与 纳奥尔–扬一九九〇年论文 对读：午餐时间这一档区分游戏对不可延展这一档相关性。
• 与 拉科夫–西蒙一九九一年论文 对读：见到挑战之后仍可访问解密的时间窗对「改不出相关明文」这句话。
• 与 密码学基础 对读：不可延展是口径上的定义，不是一份已造好的公钥，也不是改写密文或操纵投标的操作单。