随机预言机是什么

Q&A 2020-10-08 00:21:13 阅读(...)

在密码学里面,随机预言机(英语:Random oracle)是一部预言机,对任何输入都回传一个真正均匀随机的输出,不过对相同的输入,该预言机每次都会用同一方法输出。换句话说,随机预言机是一个将所有可能输入与输出作随机映射的函数。

在密码学里面,随机预言机(英语:Random oracle)是一部预言机(简单说像是理论的黑箱),对任何输入都回传一个真正均匀随机的输出(请参考离散型均匀分布),不过对相同的输入,该预言机每次都会用同一方法输出。换句话说,随机预言机是一个将所有可能输入与输出作随机映射的函数。

随机预言机是什么

限制

任何有限的函数均不是一个随机预言函数,因为随机预言机的定义要求其是一个无限大的函数。

事实上,一些刻意设计的签名和加密方式被证明如果使用随机预言机的话是安全的,但是使用其他的函式替代随机预言的话则明显不安全。另外,对任何比较自然的安全协定,在随机预言机模型之下证明为安全,是协定的“实用”可靠性的有力证据。

大体上说,一个作法被证明是安全的的话,要攻击此作法就必需要突破该证明的假设;例如,一个加密法的安全证明是基于质因数分解的困难度(像是 RSA 算法),那么打破此证明的方法就是找到快速质因数分解的算法(像是秀尔算法就被视为是一个可能的攻击)。在这里,要打破随机预言假设,我们就必须找到实际杂凑函式与随机预言机未知且不好的不同之处。对于一般被认为不存在这种弱点,够好的杂凑函式来说(这种杂凑函式现在蛮可靠的,像是 SHA-3),相关的协定因此可证明是安全的。

收藏 0个人收藏
走进科技生活方式

发表评论

登录后参与评论