随机预言机与标准模型

随机预言机模型(randomoraclemodel)中有这么个预言机oracle来回答你的问题，这个oracle怎么工作呢？它有一个列表，包含了所有可能问的问题，还有一个列表，包含了所有问题的答案，然后问题列表中的问题都被完全随机的指定了一个答案列表中的答案。在运行协议，算法的时候，需要的时候你可以问它问题，然后用他的回答继续你的运算，攻击者也可以问和获取答案。安全证明中，随机预言机模型通常是现实中哈希函数的理想化的替身。哈希函数是一个输入为任意长度，输出为固定长度的函数，单向性，抗碰撞性等。在随机预言机模型下，通常设计一个方案并证明是安全的；而在方案的实际执行时，用具体的哈希函数来替换方案中的随机预言机。在随机预言机模型下证明安全的方案在实际具体实现中未必是安全的。标准模型(StandardModel)中就没有这么个randomoracle。不依赖随机预言机的模型，称为标准模型。一般指所设计的方案（如果使用了哈希函数）在证明时，仅使用了现实中哈希函数可以实现的特性，那么可以认为是标准模型。标准模型下，敌手只受时间和计算能力的约束，而没有其他假设，如果在此条件下，可以将密码学方案归约到困难性问题上，则称为该归约是基于标准模型的，也称方案具有在标准模型下的可证明安全性。然而在实际中，很多方案在标准模型下建立安全性归约是比较困难的，也就是难于证明在安全模型下的安全性。为了降低证明的难度，往往在安全性归约过程中加入其他的假设条件，就是下面将要讨论的随机预言机模型。随机预言机模型在安全模型之上，加入了针对散列函数的随机预言机假设。这种假设下进行安全归约得到的安全性也称为随机预言机模型下的可证明安全性。随机预言机是一种散列函数，我们可以把它理解为完美的散列函数：1)一致性：对于相同的输入，其输出必然相同；2)可计算性：输出的计算可以在多项式时间内完成；3)均匀分布性：预言机的输出在取值空间内均匀分布，无碰撞。随机预言机是一种过于理想的假设，要求敌手不利用散列函数的弱点来对方案进行攻击。在现实中，并不存在这样一种完美的散列函数，因此在随机预言机模型下安全的一些方案，在使用真实的散列函数之后，就不再安全了。在现实中，散列函数是确定的，其输出并不能保证是完全随机且均匀分布的。基于随机预言机模型的安全证明除了散列函数外的环节都可以达到安全要求，目前大多数的可证明安全方案也是基于随机预言机模型的。因此，随机预言机模型仍被认为是可证明安全中最成功的应用。