随机预言机模型

形式陈述 ​

在安全参数 $\lambda$ 下，随机预言机是从输入域 ${\mathcal{X}}_{\lambda }$ 到输出域 ${\mathcal{Y}}_{\lambda }$ 均匀抽取的函数

$$H\leftarrow \mathrm{Func}({\mathcal{X}}_{\lambda },{\mathcal{Y}}_{\lambda }).$$

常见设置取 ${\mathcal{X}}_{\lambda }=\{0,1{\}}^{\ast }$、${\mathcal{Y}}_{\lambda }=\{0,1{\}}^{n(\lambda )}$，并用无歧义编码和域分离把协议上下文放入输入。诚实算法、对手以及安全证明中的模拟器都通过同一个 oracle 接口查询 $H$；同一输入永远得到同一输出。PPT 对手可以根据此前问答自适应地选择多项式次查询，完整的安全实验公理库安全实验、对手与优势函数Security experiment · Security game · Adversarial advantage以参数化交互实验和输出概率差精确定义攻击目标与对手能力的证明框架。必须说明查询预算、各方是否共享 oracle，以及挑战输入是否有额外限制。

无需在实验开始时真的抽取一张指数大甚至无限的函数表。等价的 lazy sampling 过程维护表 $T$：收到查询 $x$ 时，若 $x\in \mathrm{dom}(T)$ 就返回 $T[x]$；否则独立采样 $y\leftarrow {\mathcal{Y}}_{\lambda }$，记录 $T[x]=y$ 后返回。只要新输入的输出独立均匀、旧输入保持一致，对任何有限查询过程产生的联合分布都与预先抽取随机函数相同。

ROM 中的安全性仍以参数化游戏定义。若两个游戏都向对手开放同一个随机预言机，可写

$${\mathrm{Adv}}_A^{\mathsf{rom}}(\lambda )=|\text{Pr}[{\mathsf{G}}_0^{A,H}(1^{\lambda })=1]-\text{Pr}[{\mathsf{G}}_1^{A,H}(1^{\lambda })=1]|,$$

概率包含 $H$ 的 lazy-sampling 随机性、挑战者随机币和对手随机币；采用隐藏位成功率时，则按 $|2\text{Pr}[b^{\prime }=b]-1|$ 归一化。安全主张要求对规定能力内的每个 PPT 对手，该优势随 $\lambda$ 可忽略。

证明有时允许模拟器 programming oracle，即选择某个输入 $x^{\ast }$ 的响应来嵌入挑战或伪造一致视图。编程后的表不再是无条件独立抽取的随机函数；证明必须说明 $x^{\ast }$ 在编程前未被查询，或显式界定发生冲突时的坏事件概率，并证明对手所见分布仍与目标游戏足够接近。查询记录、查询顺序与重复输入因而是证明的一部分。

直觉 ​

随机预言机像一本所有人可查、尚未写完的随机字典：第一次查一个词时现场掷出随机释义并永久写下，以后任何人再查都看到同一结果。它理想化的不是“输出看起来杂乱”，而是对不同新输入给出独立均匀值，同时保留函数必须具备的一致性。

这种理想接口让证明能够把哈希输出当作新挑战或随机标签，并追踪攻击者是否曾问到某个关键输入。现实哈希则是一段公开、固定且结构化的代码；把它用于协议是实例化选择，不会把 ROM 里的随机函数真的实现出来。

例子与边界 ​

Fiat–Shamir 变换把三步公开币协议的挑战写成 $c=H(\mathsf{domain}\Vert x\Vert a)$，其中 $x$ 是语句、$a$ 是承诺。ROM 分析把 $c$ 视为首次查询该完整 transcript 时得到的随机挑战，并允许归约观察或在受控条件下编程这次查询。它不意味着 prover 不能反复更换 $a$ 做 grinding；对手的全部自适应查询和成功放大都必须计入实验。

一个错误实现是每次收到 $x$ 都重新独立采样响应。若同一输入先返回 $u$、后返回 $v\ne u$，诚实验证者重新计算哈希就无法复现挑战，任何依赖哈希绑定 transcript 的协议也随之失去语义。随机预言机是随机函数，不是无状态随机字符串生成器。

Oracle programming 也不能被描述成“仍然完全独立随机”。若对手已查询 $x^{\ast }$ 并看到 $y$，模拟器后来强行令 $H(x^{\ast })=y^{\prime }\ne y$，它立刻造成可观察的不一致。严谨证明通常在新鲜点上编程，或通过 guessing、rewinding、measure-and-reprogram 等技术控制差异；量子查询环境还需要单独的 QROM 分析，经典查询表论证不能原样搬用。

ROM 证明不是标准模型定理，也不是“换成任意安全哈希即可”的保证。存在专门构造的方案在随机预言机下可证安全，却在任何具体函数族实例化时都不安全。实践中选用 SHA-2、SHA-3 等标准哈希可形成有价值的设计证据，但其可信度来自 ROM 分析、具体哈希分析、域分离和协议审查的组合，而非逻辑上的自动蕴含。

推论与应用 ​

随机预言机模型广泛用于 Fiat–Shamir 签名、全域哈希 RSA、OAEP 类加密、密钥派生与非交互证明的安全分析。它让证明者以统一方式管理挑战生成、查询命中与模拟器编程，也使归约损失能够按查询数和坏事件概率明确记账。

ROM 必须与密码哈希函数公理库密码哈希函数Cryptographic hash function把任意长输入压缩到固定长度并要求原像、第二原像或碰撞难求的函数族。的现实性质分层：抗碰撞、抗原像是具体函数族在特定游戏中的计算假设，随机预言机则给出理想函数的完整查询分布。类似地，伪随机函数公理库伪随机函数Pseudorandom function · PRF由短密钥索引且对高效查询者不可与真随机函数区分的函数族。需要秘密密钥并只对高效查询者模拟随机函数；公开随机预言机对所有参与者可查询，安全实验中的观察者却仍通常受多项式资源限制。

参考资料

• Mihir Bellare and Phillip Rogaway, “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols,” CCS 1993。
• Ran Canetti, Oded Goldreich, and Shai Halevi, “The Random Oracle Methodology, Revisited,” STOC 1998; JACM 51(4), 2004。
• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，random-oracle proofs and programmable oracles。