Random Oracle Model

先看一个麻烦

你想证明一件事：「用 SHA-256 搭出来的这个协议是安全的。」

麻烦在于，SHA-256 是一个具体的、完全公开的函数。它的每一位都由一段确定的代码算出来。没有任何随机性，没有任何秘密。一个攻击者拥有和你完全相同的信息。

那「安全」是什么意思？如果你说「攻击者算不出来」，凭什么？SHA-256 是一堆加法和移位，它的输出完全由输入决定。真正的困难在于我们不知道怎么反推，而不是它在数学上不可反推。

这就是死结：你想证明一个安全性陈述，但你手上这个对象的性质没人能证明。

几个朴素猜测

猜测一：那就假设「SHA-256 不可反推」，然后往下推。

这个假设写不出来。「不可反推」要量化成什么？对哪个概率分布？用多少计算资源？更麻烦的是，SHA-256 是一个固定的函数，所以「它的输出看起来随机」这件事没有概率空间可言——你把同一个输入喂进去一百万次，得到一百万个相同的结果。

猜测二：换成一个真正随机的函数。

方向对了，但直接这么做代价很大：一个 $\{0,1\}^{256} \to \{0,1\}^{256}$ 的随机函数，要写下来得存 $2^{256} \times 256$ 位。没人能把它当参数发给协议的双方。

猜测三：不写下来，只在需要的时候现场生成。

这就对了。设想一个「预言机」：任何人可以问它 $H(x)$，它当场抛硬币决定答案，然后记住这次的回答，以后同样的 $x$ 一律给同样的答案。

从任何一方的视角，这和「有一个巨大的随机字典」完全等价，但没人需要真的存下它。这就是随机预言机模型。

机制

模型的规则只有三条：

1. 存在一个函数 $H$，从一开始就在所有可能的函数里均匀随机抽定。
2. 协议的每一方（包括攻击者）都不知道 $H$ 是什么，只能查询：给出 $x$，拿回 $H(x)$。
3. 唯一被计量的资源是查询次数。计算量不限。

        +---------------------------+
        |   随机预言机 H            |
        |   (随机抽定, 无人知晓)    |
        +---------------------------+
           ^ x        | H(x)
           |          v
     +-----+-----+  +-----------+  +-----------+
     |  Alice    |  |   Bob     |  |    Eve    |
     |  查 q_A 次|  | 查 q_B 次 |  | 查 q_E 次 |
     +-----------+  +-----------+  +-----------+

关键的一步是第 3 条。因为 $H$ 是随机的，没查过的点就是完全未知的——攻击者对 $H(x)$ 的最优猜测就是瞎猜。这把「难度」变成了一个可以数的东西：想知道 $k$ 个点的值，就得查 $k$ 次。

于是安全性证明变成了组合计数：证明攻击者要成功，必须查到某些点；再证明它查不到那么多次。Proof of Work 的安全论证就是这个形状——想找一个前导零足够多的哈希，除了逐个试没有别的办法，因为预言机不透露任何结构。

这个模型最有力的用途反而是证明做不到。1989 年 Impagliazzo 和 Rudich 用它证明：只靠单向函数，没法黑盒地造出密钥协商协议。论证的骨架是「Alice 和 Bob 之间的共同秘密只能来自预言机，而他们查过的点数是有限的，所以攻击者能把这些点全都找出来」。

为什么值得知道

这个模型给你两条能直接用的判断。

第一条：看到「在随机预言机模型下安全」，要读作一句有条件的话。

它说的是：任何攻击者，只要把哈希函数当成一个不透明的黑盒来用，就会失败。它没有说：换成真的 SHA-256 也安全。

这个缺口不是理论洁癖。Canetti、Goldreich、Halevi 在 1998 年构造出了这样的协议：在随机预言机模型下可证明安全，但换成任何具体的哈希函数都不安全。构造是刻意的、人工的，现实中没出现过这种崩塌，但它确立了一点——这一步跨越没有定理保证。

实践中的结论是：随机预言机模型下的证明是有价值的证据，不是保证。它排除掉了一大类攻击（所有把哈希当黑盒的攻击），剩下的风险是「攻击者利用了 SHA-256 的内部结构」。

第二条：黑盒不可能性结果不等于不可能。

「在随机预言机模型下无法从单向函数造出 X」这句话的准确含义是：任何只把单向函数当黑盒调用的构造都造不出 X。利用具体函数内部代数结构的构造不在约束范围内。历史上这条缝隙被反复用到，不是摆设。

所以看到一个不可能性结果时，要问的是：它禁止的是哪一类构造？我关心的那个构造在不在里面？

回到开头

一开始的死结是：想证明「用 SHA-256 搭的协议安全」，但 SHA-256 的性质没人能证明。

随机预言机模型没有解开这个结，它绕过去了。做法是把不可证明的部分整体替换成一个理想对象，然后在理想世界里做严格的数学。代价是搬回现实那一步没有定理保证——这个代价是显式的、已知的，而不是被藏起来的。

这是密码学里很常见的一种交换：用一个写在明面上的假设，换一个能真正证完的证明。比它更糟的选择是没有任何证明，只有「看起来很难破」。