转载：【密码学】可证明安全：随机预言机模型 和 标准模型

随机预言机模型：

在安全证明中，随机预言机模型通常是现实中哈希函数的理想化的替身。哈希函数是一个输入为任意长度，输出为固定长度的函数，除此之外还满足一些其它特性，例如单向性，抗碰撞性等。随机预言机的概念起源于Fiat和Shamir的把哈希函数看为随机的函数的思想，然后进一步由研究者Bellare和Rogaway转化为随机预言机模型。

在随机预言机模型下，通常设计一个方案并证明是安全的；而在方案的实际执行时，用具体的哈希函数来替换方案中的随机预言机。 应该指出，在随机预言机模型下证明安全的方案在实际具体实现中未必是安全的。

随机预言机是一种散列函数，我们可以把它理解为具有以下特性的完美的散列函数：

1)一致性：对于相同的输入，其输出必然相同；

2)可计算性：输出的计算可以在多项式时间内完成；(多项式时间:在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。)

3)均匀分布性：预言机的输出在取值空间内均匀分布，无碰撞。

在随机预言机模型中，假定敌手不会利用散列函数的弱点来攻击密码学方案。

随机预言机虽然广泛应用与密码学方案的证明，为可证明安全提供了很大的方便，但人们对随机预言机模型下的安全性证明的有效性仍存在争议的。随机预言机是一种过于理想的假设，要求敌手不利用散列函数的弱点（在现实中，散列函数是确定的， 其输出并不能保证是完全随 机且均匀分布的）来对方案进行攻击。因此在随机预言机模型下安全的一些方案，在使用真实的散列函数之后，就不再安全了。尽管如此，基于随机预言机模型的安全证明除了散列函数外的环节都可以达到安全要求，目前大多数的可证明安全方案也是基于随机预言机模型的。因此，随机预言机模型仍被认为是可证明安全中最成功的应用。