随机谕示（RandomOracle）本文介绍密码学中一个很专业的概念，该概念理解起来可能会比较难，适合对可证明安全理论感兴趣的人阅读，它为密码协议的安全性分析提供了理论工具。随机谕示模型是密码学理论的基石之一，它通过理想化假设简化了安全证明，推动了大量实用协议的设计。
随机谕示（Random Oracle）
本文介绍密码学中一个很专业的概念，该概念理解起来可能会比较难，适合对可证明安全理论感兴趣的人阅读，它为密码协议的安全性分析提供了理论工具。
随机谕示模型是密码学理论的基石之一，它通过理想化假设简化了安全证明，推动了大量实用协议的设计。它尽管存在局限性，但其方法论在可证明安全领域仍具有不可替代的价值。理解随机谕示模型的核心思想，有助于在实际应用中权衡理论安全性与工程可行性。
我们知道，密码学中的安全方案并不是凭空想象出来的，它是有安全证明的。有时候安全证明是非常困难的，在“完全严格的安全性证明”和“没有证明”之间提供一个“中间地带”，它就是随机谕示模型，该模型是一种理想模型，它可能并不能准确的反应现实，但是至少能够从理想模型下的证明中，推出一个方案设计合理性的可信度度量。只要是合理的，有证明当然比没有任何证明要好。
该模型假定了一个公共的、随机选择的函数$H$的存在。它可以被看作是一个魔盒，当给出输入$x$时，返回$H(x)$。
现实世界中随机谕示不一定真实存在，通过下面两步，随机谕示提供了一个能被用来设计和证明密码学方案安全性的方法论。
- 一个方案设计在随机谕示模型下被证明是安全的。
- 在现实世界中实现该方案时，方案中的随机谕示是用一个密码学散列函数 $\hat{H}$ 来代替的。即：当一方问询随机谕示来获得 $H(x)$ 的时候，该方就用散列函数自己计算 $\hat{H}(x)$ 来代替即可。
随机谕示模型
理解随机谕示模型可以按照如下方法：把随机谕示比作一个盒子，输入和输出都是一个二进制串，我们不需要关注盒子内部是如何工作的，只需要关注输入输出。每个人都能够和这个盒子交互，每次向盒子问询一个输入 $x$ ，盒子就会返回的输出 $y$ 作为回答，该过程可以称作向随机谕示问询 $x$ ，问询的过程是秘密的，也就是说其他人是不知道 $x$ 的，甚至不知道有人曾问询过 $x$ 。
随机谕示还有一个重要的性质，就是这个盒子的输出是一致的。即：如果有人向随机谕示问询$x$，并得到输出 $y$ ，那么再次向随机谕示问询 $x$ 时，仍然得到相同的输出 $y$ 。有了这个性质，这个盒子是不是就可以看作一个函数，答案是肯定的。
随机谕示模型下的安全证明
以下是随机谕示模型的定义，假设一个方案仅仅是通过选定 $H$ 而获得，使用 $\Pi^{H}$ 表示这种方案 $\Pi$ 是依赖随机谕示 $H$ 而获得的方案。方案 $\Pi$ 的安全性定义的一般形式如下：如果对任意概率多项式时间的敌手 $\mathcal{A}$ ，有
$$
\begin{aligned}
\mathrm{Pr}[\mathrm{Exp}{\mathcal{A}^H,\Pi^H}(n)= 1]\leq \theta+ \epsilon(n)
\end{aligned}
$$
则 $\Pi$ 是安全的。其中，$\theta$ 表示一个固定概率值，$\epsilon(n)$ 表示一个可忽略的概率值，$\mathrm{Exp}{\mathcal{A}^H,\Pi^H}$ 表示为方案 $\Pi$ 定义的安全性实验。敌手 $\mathcal{A}$ 具有访问随机谕示 $H$ 的能力。这里如果看不懂，可以先放一放，后面会有不少例子去详细说明。
随机谕示模型的简单实例
- 随机谕示构造伪随机函数
- 随机谕示作为单向函数
- 随机谕示作为抗碰撞散列函数
未完待续
