随机预言机

在密码学中，随机预言机（英语：Random oracle）是一部预言机，对任何输入都回传一个均匀且随机的输出（请参考离散型均匀分布），不过对相同的输入，该预言机每次都会用同一方法输出。换句话说，随机预言机是一个将所有可能输入与输出作随机反映的函数。

限制

只能产生有限个输出的函数均不是一个随机预言函数，因为随机预言机的定义要求其是一个有无限个输出的函数。

一些刻意设计的签名和加密方式被证明如果使用随机预言机的话是安全的，但是使用其他的函式替代随机预言的话则明显不安全。^[1] 另外，对任何比较自然的安全协定，在随机预言机模型之下证明为安全，是协定的“实用”可靠性的有力证据。

一个作法被证明是安全的的话，要攻击此作法就必需要突破该证明的假设；例如，一个加密法的安全证明是基于质因数分解的困难度（像是RSA演算法），那么打破此证明的方法就是找到快速质因数分解的演算法（像秀尔演算法就是一个可能的攻击）。要打破随机预言假设，我们就必须找到实际杂凑函式与随机预言机未知且不好的不同之处。对于一般被认为不存在这种弱点，够好的杂凑函式来说（这种杂凑函式现在被认为是可靠的，像是SHA-3），相关的协定因此可证明是安全的。

杂凑函数与随机预言机的关联

在密码学中，杂凑函式（Hash Function）是一种将输入映射到固定长度输出的函数，并广泛应用于数据完整性验证、数位签章和密码学协定中。然而，现实中的杂凑函数（如 SHA-256）并不完全符合理想的随机预言机模型，因为它们是确定性的（Deterministic）且基于具体演算法设计，而非真正的随机函数。 然而，在许多密码学证明中，研究者会假设杂凑函数表现得类似于随机预言机，并使用随机预言机模型来分析加密协议的安全性。例如，数位签章演算法（如 RSA-PSS）和密码金钥派生函数（如 HKDF）都在其安全性分析中使用了这一模型。

这种方法被称为随机预言机启发（Random Oracle Heuristic），尽管在理论上某些 Hash 函数可能会与随机预言机有所不同，但它仍然是一种实用且广泛接受的安全性分析技术。

相关条目

• 预言机
• 标准模型 (密码学)
• 密码学主题列表
• 图灵机
• 图灵归约
• 交互式证明系统
• 杂凑函式