随机谕示（RandomOracle）本文介绍密码学中一个很专业的概念，该概念理解起来可能会比较难，适合对可证明安全理论感兴趣的人阅读，它为密码协议的安全性分析提供了理论工具。随机谕示模型是密码学理论的基石之一，它通过理想化假设简化了安全证明，推动了大量实用协议的设计。
随机谕示（Random Oracle）
本文介绍密码学中一个很专业的概念：随机谕示，不过也有人称它为随机预言机，但都指的是一个东西，本人更倾向于用随机谕示，因为此概念比较理想化，行为就像一个神明一样传达神谕、预言或指令，神谕一旦下达，就会被认为神圣而不可质疑的。该概念理解起来可能会比较晦涩难懂，适合对可证明安全理论感兴趣的人阅读，它为密码协议的安全性分析提供了理论工具。
随机谕示模型是密码学理论的基石之一，它通过理想化假设简化了安全证明，推动了大量实用协议的设计。它尽管存在局限性，但其方法论在可证明安全领域仍具有不可替代的价值。理解随机谕示模型的核心思想，有助于在实际应用中权衡理论安全性与工程可行性。
了解过零知识证明这块的人知道 Fiat-Shamir 变换的安全性分析就是基于随机谕示模型的，将一个交互式协议转变成一个公开可验证的非交互式协议。当然还可以应用到数字签名、身份认证、区块链协议中。
我们知道，密码学中的安全方案并不是凭空想象出来的，它是有安全证明的。有时候安全证明是非常困难的，在“完全严格的安全性证明”和“没有证明”之间提供一个“中间地带”，它就是随机谕示模型，该模型是一种理想模型，它可能并不能准确的反应现实，但是至少能够从理想模型下的证明中，推出一个方案设计合理性的可信度度量。只要是合理的，有证明当然比没有任何证明要好。
该模型假定了一个公共的、随机选择的函数 $H$ 的存在。它可以被看作是一个魔盒，当给出输入 $x$ 时，返回 $H(x)$ 。
现实世界中随机谕示不一定真实存在，通过下面两步，随机谕示提供了一个能被用来设计和证明密码学方案安全性的方法论。
- 一个方案设计在随机谕示模型下被证明是安全的。
- 在现实世界中实现该方案时，方案中的随机谕示是用一个密码学散列函数 $\hat{H}$ 来代替的。即：当一方问询随机谕示来获得 $H(x)$ 的时候，该方就用散列函数自己计算 $\hat{H}(x)$ 来代替即可。
随机谕示模型
理解随机谕示模型可以按照如下方法：把随机谕示比作一个盒子，输入和输出都是一个二进制串，我们不需要关注盒子内部是如何工作的，只需要关注输入输出。每个人都能够和这个盒子交互，每次向盒子问询一个输入 $x$ ，盒子就会返回的输出 $y$ 作为回答，该过程可以称作向随机谕示问询 $x$ ，问询的过程是秘密的，也就是说其他人是不知道 $x$ 的，甚至不知道有人曾问询过 $x$ 。
- 性质 1.1：随机谕示的输出是一致的。即：如果有人向随机谕示问询 $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$ 的能力。这里如果看不懂，可以先放一放，后面会有不少例子去详细说明。
随机谕示模型的简单实例
不妨假设一个随机谕示，其输入长度为 $n_1$，输出长度为 $n_2$，满足 $n_1,n_2\geq n$，$n$ 表示安全参数。
-
随机谕示构造伪随机函数\
伪随机函数是有严格定义的，这里可以先简单的理解为一个带有秘密的函数。怎么利用随机谕示构造一个伪随机函数呢？定义如下：\
$F_k(x)=H(k||x)$，其中$H$是随机谕示，不妨假设$H$的输出长度是$n_2=n$，输入长度是$n_1=2n$。可以声称上述定义是一个伪随机函数。构造起来比较容易，不过证明是非常困难的。
-
随机谕示作为单向函数\
首先这里并不是说随机谕示是单向函数，但是它可以像单向函数那样工作，这里声称任意一个概率多项式时间的敌手 $\mathcal{A}$ 在下面的实验中成功的概率是可以忽略的：
实验 $\text{Exp1}:$ \
(1) 随机选取一个伪随机函数 $H$\
(2) 随机选取 $x\in{0,1}^{n_1}$ ，并计算 $y:=H(x)$\
(3) 敌手 $\mathcal{A}$ 拿到 $y$，如果 $\mathcal{A}$ 输出一个值 $x'$，满足 $H(x')==y$，则成功。
这里敌手$\mathcal{A}$可以询问随机谕示$H$任意多次，事实上任何人都可以询问随机谕示，因为在现实方案中会用具体函数来代替随机谕示，该函数是已知的任何人都可以计算该函数，包括敌手。
现在证明对于任意概率多项式时间的敌手 $\mathcal{A}$ 在上面的实验中成功的概率是可忽略的。
实验$\text{Exp2}:$\
(1) 随机选取一个 $x\in {0,1}^{n_1}$ ，随机选取一个 $y\in{0,1}^{n_2}$ ，并将 $y$ 指定给$\mathcal{A}$。\
(2) 对于 $\mathcal{A}$ 每次向随机谕示询问 $x_i$ ，做出如下工作：
- 如果 $x_i==x$ ，则 $\mathcal{A}$ 成功。
- 否则，随机选取 $y_i\in{0,1}^{n_2}$，如果 $y_i==y$，则 $\mathcal{A}$ 成功，否则，将 $y_i$ 作为回答返回给 $\mathcal{A}$，并继续实验。
假设 $\mathcal{A}$ 询问随机谕示的次数是 $q$ ，并且不会重复询问（其实重复询问也没问题，只需要用重复的问询 $x_i$ 对应的 $y_i$ 再次作答即可），因为 $\mathcal{A}$ 运行多项式时间，所以 $q=poly(n)$ 。因为 $y$ 独立于 $x$ ，对于某个询问，事件 $x_i==x$ 发生的概率最多是 $q/{2^{n_1}}$ 。当 $x_i\neq x$ 时，事件 $y_i==y$ 发生的概率最多是 $q/{2^{n_2}}$。于是事件 $\mathcal{A}$ 成功发生的概率最多是 $\frac{q}{2^{n_1}}+\frac{q}{2^{n_2}}\le\frac{2q}{2^n}$，因为 $n_1,n_2\ge n$，该概率显然是可忽略的。
经过分析，随机谕示表现得像一个单向函数一样，不同的是单向函数是一个具体的函数，满足求原像是困难的，而随机谕示作为一个理想化的角色，当有人向随机谕示问询 $x$ 时，只需要随机选择一个 $y$ 作为回答即可，当敌手拿到 $y$ 之后，敌手是不知道 $x$ 的，敌手试图去找一个 $x'$，使得随机谕示的回答是 $y$。敌手拥有访问随机谕示的能力，如果敌手在某次问询中恰好问询到 $x$，根据随机谕示的性质 1.1，此时随机谕示必须输出 $y$，此时敌手输出 $x$，敌手成功；如果敌手询问到某个$x'\ne x$，但是随机谕示的输出恰好也是 $y$，此时敌手输出 $x'$，敌手同样成功。
-
随机谕示作为抗碰撞散列函数\
随机谕示表现得像一个抗碰撞哈希函数是很容易做到的。对于任意的概率多项式时间的敌手$\mathcal{A}$，在下面的游戏中成功的概率是可忽略的。
实验 $\text{Exp3}:$\
(1)选择一个随机函数 $H$\
(2)如果 $\mathcal{A}$ 输出 $x,x'$，满足 $H(x)==H(x')$ 且 $x\ne x'$，则 $\mathcal{A}$ 成功。
上述实验中，敌手 $\mathcal{A}$ 拥有询问随机谕示的能力，不妨假设询问次数为 $q=poly(n)$，记为 $x_1,x_2,\dots,x_q$，敌手输出两个值 $x_i\ne x_j$，根据生日攻击原理，事件 $H(x_i)==H(x_j)$ 的概率最多为 $\frac{q^2}{2^{n_2}}$，该概率是可忽略的。
高级阶段
-
基于随机谕示模型的选择明文攻击 (CPA) 安全的公钥加密
-
基于随机谕示模型的选择密文攻击 (CCA) 安全的公钥加密
未完待续
