密码学与信息安全
可证明安全性
根据所基于的不同理论，可分为信息论安全（I
formatio
TheorySecurity）和计算复杂性安全（Computatio
alComplexitySecurity）两大类。信息论安全由CSha
o
在其开创性的文献12中给出定义，一个方案如果满足信息论安全，那么无论攻击者具有什么样的计算能力都无法破解，所以信息论安全又被称为无条件安全。虽然信息论安全在安全上是完美的，但却有着难以实用的缺点，因而只是用在军事和外交等对信息保密极度敏感的领域。计算复杂性安全是基于复杂性理论之上的一套模型，它将攻击者的能力限定为多项式时间，一个方案是否安全取决于攻击者成功的优势能否规约到以不可忽略的概率解决某个已知困难问题，例如大整数分解，二次剩余，离散对数等。计算复杂性安全虽然并不能保证无条件安全（例如在量子计算机中大数分解问题不再是困难的），并且对攻击者的能力加以了限制，但在理论下的攻击者的计算能力实际上已远远超过现实当中存在的攻击者，因而计算复杂性安全模型下的方案在实际应用中仍然是可以信赖的。因而在现实环境当中，攻击者在计算能力上并无任何特别的优势可言。
标准模型标准模型
早期基于计算复杂性安全的密码方案一般是基于标准模型（Sta
dardModel）下，该模型首先对方案中攻击者的能力加以定义，而且必须强调攻击者一定是自适应性的。然后假设该攻击者成功的概率为某个多项式时间不可忽略的值，然后通过一定的步骤利用该攻击者，将攻击者的能力转化为攻破某已知困难问题的优势。由于该困难问题在多项式时间下无法求解，因而可以得出存在攻击者以不可忽略概率攻破方案这一假设与事实相矛盾。不幸的是，基于标准模型的密码方案往往需要大量的计算，难以实用。如现有最高效的标准模型下安全的公钥加密方案，数字签名方案，仍然没有广泛加以使用。如何设计一个面向具体应用的密码方案，同时平衡可证明安全性和实用性，成为了密码方案设计中首要考虑的问题。因为一个低效率的方案与不安全的方案一样，都无法在实际当中被广大用户接受并广泛使用。
随机预言机模型的定义
虽然计算复杂性安全模型下的方案已经比信息论安全模型下的方案更加实用，但仅从标准模型下的现有绝大部分方案来看，都无法在实际当中推广开来，造成了密码学理论和实践中的一个鸿沟原因在于有许多广泛应用的方案虽然无法给出标准模型下的证明，但在长期应用中抵御住了实际的攻击者，取得了大众的信任。同时标准模型下设计一个安全r