随机预言机模型的定义
随机预言机（ Oracle） 随机预言机（Random Oracle）的定义是一个确定性的公共 可访问的随机均匀分布函数（ Distributed）， 可访问的随机均匀分布函数（Uniformly Distributed）， 对于任意长度的输入， 对于任意长度的输入，在输出域中均匀选择一个确定性长 度的值作为询问的回答。 度的值作为询问的回答。 随机预言机模型是在标准模型的基础上增加了一个公共可 访问的随机预言机，将方案中所使用的散列函数（ 访问的随机预言机，将方案中所使用的散列函数（Hash Function）理想化为随机预言机，攻击者（Adversary） Function）理想化为随机预言机，攻击者（Adversary）只 能通过询问随机预言机来获得所需要的散列值（ 能通过询问随机预言机来获得所需要的散列值（Hash Value）。然后仿真者（Simulator） ）。然后仿真者 Value）。然后仿真者（Simulator）通过一定的步骤利用 该攻击者， 该攻击者，将攻击者的能力转化为攻破某已知困难问题的 优势（Advantage）。 优势（Advantage）。
随机预言机模型的定义
[1]M.Bellare and P.Rogaway.Random oracles are practical-a paradigm for designing efficient protocols.In Proceedings of the First ACM Conference on Computer and Communications Security,pages 62– 73,1993. [2]M.Bellare and P.Rogaway.The exact security of digital signatureshow to sign with rsa and rabin. In U.Maurer, editor,Advances in Cryptology-Proceedings of EUROCRYPT’96,volume LNCS ’ 1070,pages 399–416,1996. [3]M.Bellare and P.Rogaway.Optimal asymmetric encryption—how to encrypt with rsa.In Advances in Cryptology– EUROCRYPT’94,volume LNCS 950,pages 92–111.Springer’ Verlag,1995. [4]E.Fujisaki and T.Okamoto.Secure integration of asymmetric and symmetric en- cryption schemes.In Advances in CryptologyCrypto’99,volume LNCS 1666,pages537–554,1999. ’
随机预言机模型的定义
虽然计算复杂性安全模型下的方案已经比信息论安全 模型下的方案更加实用， 模型下的方案更加实用，但仅从标准模型下的现有绝 大部分方案来看，都无法在实际当中推广开来， 大部分方案来看，都无法在实际当中推广开来，造成 了密码学理论和实践中的一个鸿沟. 了密码学理论和实践中的一个鸿沟. 原因在于有许多广泛应用的方案虽然无法给出标准模 型下的证明，但在长期应用中抵御住了实际的攻击者， 型下的证明，但在长期应用中抵御住了实际的攻击者， 取得了大众的信任。 取得了大众的信任。同时标准模型下设计一个安全的 方案十分困难，没有形成一套方法论， 方案十分困难，没有形成一套方法论，方案的设计成 为一种科学艺术,而非工程。 为一种科学艺术,而非工程。 这种状况在1993年 Bellare和Rogaway创造性地提出 这种状况在1993年，Bellare和Rogaway创造性地提出 1993 随机预言机模型后[1] 取得了飞跃性的进步。 [1]， 随机预言机模型后[1]，取得了飞跃性的进步。
密码学与信息安全
可证明安全性
根据所基于的不同理论，可分为信息论安全（ 根据所基于的不同理论，可分为信息论安全（Information Theory Security）和计算复杂性安全（Computational Complexity ）和计算复杂性安全（ Security）两大类。 ）两大类。 信息论安全由C.Shannon在其开创性的文献 在其开创性的文献[12]中给出定义，一个方 中给出定义， 信息论安全由 在其开创性的文献 中给出定义 案如果满足信息论安全， 案如果满足信息论安全，那么无论攻击者具有什么样的计算能力都无 法破解，所以信息论安全又被称为无条件安全。 法破解，所以信息论安全又被称为无条件安全。虽然信息论安全在安 全上是完美的，但却有着难以实用的缺点， 全上是完美的，但却有着难以实用的缺点，因而只是用在军事和外交 等对信息保密极度敏感的领域。 等对信息保密极度敏感的领域。 计算复杂性安全是基于复杂性理论之上的一套模型， 计算复杂性安全是基于复杂性理论之上的一套模型，它将攻击者的能 力限定为多项式时间， 力限定为多项式时间，一个方案是否安全取决于攻击者成功的优势能 否规约到以不可忽略的概率解决某个已知困难问题，例如大整数分解， 否规约到以不可忽略的概率解决某个已知困难问题，例如大整数分解， 二次剩余，离散对数等。 二次剩余，离散对数等。 计算复杂性安全虽然并不能保证无条件安全（ 计算复杂性安全虽然并不能保证无条件安全（例如在量子计算机中大 数分解问题不再是困难的），并且对攻击者的能力加以了限制， ），并且对攻击者的能力加以了限制 数分解问题不再是困难的），并且对攻击者的能力加以了限制，但在 理论下的攻击者的计算能力实际上已远远超过现实当中存在的攻击者， 理论下的攻击者的计算能力实际上已远远超过现实当中存在的攻击者， 因而计算复杂性安全模型下的方案在实际应用中仍然是可以信赖的。 因而计算复杂性安全模型下的方案在实际应用中仍然是可以信赖的。 因而在现实环境当中，攻击者在计算能力上并无任何特别的优势可言。 因而在现实环境当中，攻击者在计算能力上并无任何特别的优势可言。
随机预言机模型下可证明安全过程
由于事先确定的挑战包含有仿真者可用来解答方 案所基于的困难问题的知识（Knowledge） 案所基于的困难问题的知识（Knowledge），如果 仿真游戏成功的概率为不可忽略的值，那么必然 仿真游戏成功的概率为不可忽略的值， 方案所基于的困难问题在给定攻击者的环境下不 再是困难的， 再是困难的 ， 这与现实环境中该已知困难问题的 不可计算性（ Intractable） 不可计算性（Computational Intractable）相矛 因而该攻击者实际是不存在的， 盾 ， 因而该攻击者实际是不存在的 ， 方案在模型 下是安全的。 下是安全的。
标准模型
早期基于计算复杂性安全的密码方案一般是基于标准模型 （Standard Model）下，该模型首先对方案中攻击者的 ） 能力加以定义，而且必须强调攻击者一定是自适应性的。 能力加以定义，而且必须强调攻击者一定是自适应性的。 然后假设该攻击者成功的概率为某个多项式时间不可忽略 的值，然后通过一定的步骤利用该攻击者， 的值，然后通过一定的步骤利用该攻击者，将攻击者的能 力转化为攻破某已知困难问题的优势。 力转化为攻破某已知困难问题的优势。由于该困难问题在 多项式时间下无法求解， 多项式时间下无法求解，因而可以得出存在攻击者以不可 忽略概率攻破方案这一假设与事实相矛盾。 忽略概率攻破方案这一假设与事实相矛盾。幸的是，基于标准模型的密码方案往往需要大量的计算， 难以实用。如现有最高效的标准模型下安全的公钥加密方 难以实用。 案]，数字签名方案 ，仍然没有广泛加以使用。如何设计 ，数字签名方案]，仍然没有广泛加以使用。 一个面向具体应用的密码方案，同时平衡可证明安全性和 一个面向具体应用的密码方案， 实用性，成为了密码方案设计中首要考虑的问题。 实用性，成为了密码方案设计中首要考虑的问题。因为一 个低效率的方案与不安全的方案一样， 个低效率的方案与不安全的方案一样，都无法在实际当中 被广大用户接受并广泛使用。 被广大用户接受并广泛使用。
随机预言机模型下可证明安全过程
在随机预言机模型下， 在随机预言机模型下 ， 我们将整个证明过程定义 为一个仿真游戏（Game） 为一个仿真游戏（Game）。 在模型中除了随机预言机之外， 在模型中除了随机预言机之外 ， 还存在一个仿真 Simulator， 简称Simon Simon） 者 （ Simulator， 简称 Simon）， 该仿真者对攻击 Adversary，简称MALICE MALICE） 者（Adversary，简称MALICE）所有定义的询问进 行回答，这一过程被称之为训练（Trainning） 行回答，这一过程被称之为训练（Trainning）。 在仿真游戏的最后，仿真者Simon Simon给出事先确定的 在仿真游戏的最后，仿真者Simon给出事先确定的 挑战（Challenge） 如果攻击者MALICE完成挑战， MALICE完成挑战 挑战（Challenge），如果攻击者MALICE完成挑战， 则仿真游戏成功。
随机预言机模型的定义
在实际应用中, 在实际应用中,一般用一个安全的散列函数来替代随机预 言机, 言机,方案的安全性便基于可证明安全的规约结果和散列 函数本身与随机预言机的可区分性之上。 可区分性之上 函数本身与随机预言机的可区分性之上。 散列函数与随机预言机相似的性质（快速，确定，单向， 散列函数与随机预言机相似的性质（快速，确定，单向， 均匀分布） 均匀分布）使其在密码方案设计中扮演了非常重要的角 实际上， 色。实际上，对某个消息进行散列运算之后再处理可以 增加该消息的冗余度， 增加该消息的冗余度，从信息论安全的角度来看是十分 有益的。 有益的。 同时与标准模型下可证明安全的方案相比较， 同时与标准模型下可证明安全的方案相比较，方案的计 算开销也会因为随机预言机模型下许多紧规约技巧而大 大降低。 大降低。
随机预言机的类型
在基于随机预言机模型下的密码方案的证明当中， 使用随 在基于随机预言机模型下的密码方案的证明当中， 机预言机的方法也有不同， 机预言机的方法也有不同，从仿真者对随机预言机加以控制 的程度不同可以分为以下三种类型： 的程度不同可以分为以下三种类型：