Bellare–Rogaway 1993：为什么先把哈希当成公开的随机预言机

破除误解：随机预言机不是已经造好的哈希，可证明也不是一份伪造教程#

第一种最快的读法是：把贝拉雷–罗加韦听成 1994 年那份填充，或听成 1986 年菲亚特–沙米尔把交互识别压成哈希提问，或听成 1998 年卡内蒂–戈德赖希–哈勒维的不可实例化，或听成克拉默–肖普的标准模型。费尔法克斯印在封面上：第一届 CCS、十一月、ACM，页码 62 至 73。次年 EUROCRYPT 是另一条讲义链。五年后的 STOC 是另一场反例。把四份印刷收成一句「随机预言机那篇」，会把宣言、填充、反例与标准模型焊成一次页码。

第二层常见读法把随机预言机当成实验室里已经配好的 SHA-1，或当成密钥编制表。十二页里的对象先是一枚公开的随机函数：协议里的每一方、包括对手，都可以拿字符串去询问，收回一个看起来均匀随机的答案；同一询问必须得到同一答案。没有人私藏这枚函数。

对手问哈希，得到的是窗口当场给出的答案，不是某台机器里已经写死的压缩表。公开不等于次数不限：询问仍被多项式资源卡住。这和带密钥的伪随机函数不是同一装置。卢比–拉科夫一九八八年把观察者挡在密钥之外；本页把函数放进公共场地。把「公开」听成「已经实现」，会把模型语言收成产品规格。

第三层容易把归约听成一份伪造日程，或把「对预言机编程」听成教人去改哈希实现。原文把证明写成对话：归约扮演哈希窗口，自己选定答案，必要时把伪造者倒带，再换一套答案。若伪造仍然交得出合法签名，缝就被送回陷门置换的求逆。倒带与设定答案都属于存在性归约的内部语言。本页停在「证明如何对预言机说话」，不把询问次序写成检测步骤，也不提供如何拼装伪造、如何利用填充缺口的操作。

还有一种收法把「可证明安全」听成最后那一跳也已经被证完。十二页自己把替换写成启发式。随机预言机里的定理，在把预言机换成 SHA-1 一类哈希之后，并不自动还在。作者承认这一步跨出了定理语句。

后年卡内蒂、戈德赖希与哈勒维给出不可实例化的反例，说明这不是修辞。1993 年尚未写下那条反例。它写下的是：先在理想化窗口里交出高效方案，再把窗口换成真实哈希，中间隔着作者自己标出的缝。

公开的随机函数、对预言机编程，以及最后那一跳#

装置从理论与实践之间的粒度缺口开始。戈德瓦塞尔与米卡利 1984 年把公钥加密的安全写成语义安全：多项式观察者看见密文，不该多知道明文的任何可计算函数。口径很干净，第一次实现却按比特拉长密文。纳奥尔–扬与拉科夫–西蒙继续加码对手类，合法密文后面吊着非交互证明。标准模型里「可证明」与「可写出、跑得动」当时离得很开。十二页要问的是：若允许协议调用一枚公开随机函数，高效的加密与签名能否重新变成可归约的对象。

随机预言机不是密钥。任何人都可以询问。答案在第一次被问到时均匀抽出，之后保持一致。协议把「哈希」写成对这扇窗口的调用，而不是写成某一份压缩函数的内部状态。

证明因此可以「对预言机说话」。它看见询问内容，选定看起来随机的答案，并记下对应，以便稍后回答签名询问。倒带把伪造者拉回某一时刻，换一套尚未固定的答案。对外，窗口仍然像一枚随机函数；对内，窗口是归约的工作纸。本页不把工作纸上的对应写成该去收集的样本。这是模型许可，不是一份去改实现的说明书。

签名展品后来被叫做全域哈希风格。消息先进入哈希窗口，摘要必须落在陷门置换的整个定义域上，再由持有陷门的人求逆。姚期智 1982 年已经把陷门函数写成正算容易、反算需要私藏的对象；RSA 是课堂最常见的那一枚燃料。十二页不把模幂焊成产品。

它问的是：在预言机可被设定的世界里，一份成功的伪造能否翻译成一次求逆。归约对外回答哈希询问。对大多数消息，它把答案设成自己能求逆的像，以便回答签名询问。对其中一枚消息，它把求逆挑战嵌进去。

伪造者若恰好在那一枚上交卷，归约就得到原像。必要时把伪造者倒带，是为了让「恰好」这件事以不可忽略的概率发生。这是存在性翻译，不是伪造教程。

加密展品走同一扇窗口。随机种子被送进陷门置换，预言机再把种子扩成掩码，罩住明文。合法收信人用陷门找回种子，再向同一扇窗口要回掩码。证明同样靠设定答案：归约不必先知道明文，也能让密文总体在多项式观察者面前叠在一起。形状是模型里的对象，不是填充字节的装配图。次年的 OAEP 把「最优膨胀」写成另一套填充；那是 1994 年的封面。

最后那一跳被原文自己标出来。设计与证明都在随机预言机里完成。部署时把窗口换成 MD5 或 SHA-1 一类的压缩哈希。定理语句在替换之后不再自动成立。

作者没有声称这类函数在数学上等于随机预言机。他们声称的是一种工程判断：先在理想窗口里把方案写短、把归约写清，再把窗口换成当时已经在用的哈希。若真实哈希露出协议能咬住的结构，启发式就失效。失效被写成提醒，不是写成一份寻找结构的手册。

十二页没有证明任何具体哈希族「像随机预言机」。它也没有裁决单向函数是否存在，更没有裁决 $P$ 对 $NP$。随机算法总览里的硬币常常为了把错误界压低；这里的随机性先属于那枚公开函数，硬币是模型里的理想对象，不是编码轮数表。

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

它证明了：在所有参与者都可询问一枚公开随机函数的模型里，可以写出高效的签名与加密，并把它们的安全口径归约到陷门置换的求逆。全域哈希风格的签名是展品：若存在概率多项式时间的伪造者，就存在把该伪造翻译成求逆的归约；翻译手续包括设定哈希答案，以及在需要时倒带伪造者。加密展品把种子与掩码交给同一扇窗口。

它测到的是模型内部的翻译：伪造或区分一旦发生，求逆就发生。它没测到窗口被真实哈希替换之后翻译是否还在。后一句被留给启发式，而不是留给另一条定理。它给出的是设计范式，不是一份已上线的密码套件。安全性相对「预言机仍在」这一句模型假设成立。这句话不是操作单。

它没有证明真实哈希可以替换预言机。十二页把替换标成启发式，停在那里。它没有覆盖菲亚特–沙米尔 1986 年那一次把交互提问换成哈希；那是识别协议的非交互化，不是本页的范式宣言。它没有覆盖 1994 年的 OAEP。

它没有覆盖卡内蒂–戈德赖希–哈勒维后来写下的不可实例化：存在只在预言机里安全、对任意具体函数都不安全的人造方案。它没有给出克拉默–肖普那种不把哈希升成公开随机函数、仍在判定性迪菲–赫尔曼上挡住自适应选择密文的装置。它没有重写午餐时间或见到挑战之后那两档对手类的第一次存在性。它更没有把 RSA 模幂写成产品规格。

预言机必须对所有人开放，证明才看得见询问、才设定得了答案。换成真实哈希之后，询问不再经过归约的窗口，翻译手续就没有着落。

对照属于 计算复杂性 地图与 密码学基础 总览。高效换来的是一句额外的启发式。1993 年把这句启发式写在明处。后年的反例说明，它不是可以随手抹掉的注释。

跨域连接#

• 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把被动窃听下的密文总体写成多项式不可区分，第一次实现却按比特拉长。本页假定那句口径已经在那儿，再问公开随机函数能否把「可证明」重新接到可写出的短密文与短签名上。把 1993 年听成又一篇语义安全定义，会把模型许可收成一次二次剩余判定。
• 姚期智一九八二年陷门函数论文：芝加哥那十二页把陷门与计算不可区分写成共用装置。本页把陷门当作燃料，把测试者升级成「还可以询问并观察一枚公开随机函数」的归约。没有陷门，伪造翻译不成求逆；没有预言机，归约看不见哈希窗口。把两篇听成已经配好哈希，会把存在性燃料收成一次压缩函数。
• 卢比–拉科夫一九八八年论文：那十四页从带密钥的伪随机函数交出询问下仍像随机的置换。密钥是私藏的。本页的随机函数没有密钥，对敌我双方都开放。把「像随机的函数」收成同一对象，会把私藏的轮函数与公开的预言机并进一次装置。
• 克拉默–肖普一九九八年论文：那十三页拒绝把哈希升成公开随机函数，改在判定性迪菲–赫尔曼与抗碰撞核验上挡住自适应选择密文。本页走的是另一条粒度：先把哈希理想化，再承认实例化是额外一跳。把 1998 年听成已经给 1993 年补了标准模型证明，会把启发式缝抹掉。
• 贝拉雷–罗加韦一九九四年 OAEP：次年那一篇把随机预言机里的加密收成一套有膨胀主张的填充，燃料常被取成 RSA。本页是前一年的范式宣言，展品还停在「可以这样设计」，没有把最优填充写成封面。两篇同一对作者，两条讲义链。
• 拉科夫–西蒙一九九一年论文：那十二页把选择密文的时间窗留到见到挑战之后，撑住窗口的是可抽取的非交互知识证明。本页不重写那一档对手类，也不把证明系统吊回密文后面。它问的是哈希窗口本身能否成为高效方案的证明资源。
• 纳奥尔–扬一九九〇年论文：午餐时间停在见到挑战之前，附属物是同文语言上的非交互零知识。本页的效率主张不走那条证明系统。把两篇听成同一份「更强安全」，会把对手类与哈希模型收成一次印刷。
• 交互式证明与零知识：总览里菲亚特–沙米尔变换把验证者的硬币换成哈希，好消除交互。本页是七年后的邻居：系统地把「哈希当成公开随机函数」写成设计方法，而不是再证一次识别协议的非交互化。两条缝是同一类启发式，封面不是同一页。
• RSA 公钥密码：算法页管模幂与填充。全域哈希风格把 RSA 一类陷门置换当作燃料，并不把模数长度表写成 1993 年的产品规格。把封面听成 RSA 的安全补丁，会把范式收成一次工程修订。
• 密码学基础：总览需要「标准模型」与「随机预言机」两档证明世界，也需要作者自己标出的实例化缝。本页提供 1993 年把第二档写成可设计范式的那一次。它没有把压缩函数的内部循环写成步骤。
• 加密基础：入门页把对称、公钥与哈希收成地图。本页只抽出哈希在证明里被当成公共随机装置的那一次。地图上后来出现的填充与混合加密，都不在页码 62 至 73。
• 沙菲·戈德瓦塞尔：人物页管定义先于方案。本页是后十年把语义安全口径接到高效装置上的一种方法，作者名单里没有戈德瓦塞尔。把十二页听成人物评传，会把随机预言机收成一条生平。

参考文献#

• Mihir Bellare & Phillip Rogaway, "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols", Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, 3–5 November 1993, pp. 62–73. DOI: 10.1145/168588.168596. ACM ISBN: 0-89791-629-8. —— 本文对象。
• Amos Fiat & Adi Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems", Advances in Cryptology — CRYPTO '86, LNCS 263, Springer, 1987, pp. 186–194. DOI: 10.1007/3-540-47721-7_12. —— 前邻：交互识别的非交互化，不是本页封面。
• Mihir Bellare & Phillip Rogaway, "Optimal Asymmetric Encryption", Advances in Cryptology — EUROCRYPT '94, LNCS 950, Springer, 1995, pp. 92–111. DOI: 10.1007/BFb0053428. —— 次年 OAEP，不是本页封面。
• Ran Canetti, Oded Goldreich & Shai Halevi, "The Random Oracle Methodology, Revisited", Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 209–218. DOI: 10.1145/276698.276741. —— 后年：随机预言机方法论的不可实例化反例。
• Ran Canetti, Oded Goldreich & Shai Halevi, "The Random Oracle Methodology, Revisited", Journal of the ACM 51(4), 2004, pp. 557–594. DOI: 10.1145/1008731.1008734. —— 上一条的期刊扩写。
• 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. —— 标准模型邻居，不是本页封面。
• 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. —— 语义安全的先行文本。
• 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. —— 陷门燃料的先行文本。
• 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 Luby & Charles Rackoff, "How to Construct Pseudorandom Permutations from Pseudorandom Functions", SIAM Journal on Computing 17(2), April 1988, pp. 373–386. DOI: 10.1137/0217022. —— 带密钥的伪随机函数邻居，不是公开预言机。
• 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. —— 午餐时间前邻。
• 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. —— 自适应时间窗前邻。

延伸阅读#

• 与 贝拉雷–罗加韦一九九四年 OAEP 对读：范式宣言对填充方案，同一对作者、两条讲义链。
• 与 克拉默–肖普一九九八年论文 对读：公开随机函数上的启发式，对标准数论上可写出的核验。
• 与 密码学基础 对读：随机预言机是证明世界，不是一份已造好的哈希，更不是伪造教程。