AlexiaChen.github.io icon indicating copy to clipboard operation
AlexiaChen.github.io copied to clipboard

Published 20 hours ago • verified publisher icon AlexiaChen

随机预言机(Random Oracles)是什么?

Open AlexiaChen opened this issue 4 years ago • 0 comments

正文

在很多密码学的论文里面都可以看到这个概念，特别是安全性相关的证明章节中，这是一个前提假设(assumption)。

打个比方:

随机预言机模型(ROM)被描述为以下模型:

  • 有个黑盒，盒子里面住着一个侏儒，还有一本书和一些骰子。
  • 我们可以给任意二进制位序列作为黑盒的输入
  • 给定一些侏儒事先没有见过的输入数据，然后侏儒使用它的骰子随机均匀地生成一个新的输出，然后侏儒再把这对<input,ouput>的元组数据记录在它的书中
  • 如果输入数据侏儒之前就见到过了（在它的书中找到了对应的输入数据），那么侏儒就从它书中记录的对应最后一次返回的输出，并将这个输出再次返回

再举个具体的例子

书中记录了以下元组: <"123", "ada"> <"21", "kk"> <"4223", "89gy">

现在又给了一个输入进去，假设是“123”， 那么侏儒在它书中找到了元组<"123", "ada">, 那么它将把<"123", "ada">的输出"ada"返回出去，因为这个元组记录是最后一次的返回输出记录。（相同输入，返回相同输出）

好了，这样就比较直观了，这么看来，随机预言机好像一个hash函数，只是这个hash函数对于相同的输入对应的是不同的输出。也就是我们根本不知道消息m对应的输出是什么，直到我们去尝试输入m。这就在密码学的安全证明中是个有用的工具，因为它可以用调用预言机的次数来表示攻击的努力程度。

随机预言机真正的问题在于，现实中很难构建一个真正的“随机”预言机。因为显然，在那个黑盒中没有证据表明存在这样一种在另外的神秘空间（黑盒）中扮演神秘的上帝公平视角的侏儒存在。

所以这个预言机的候选者只能是Hash函数了。一个安全的散列函数意味着对冲突、原像(preimage)和第二原像(second preimage)具有抵抗性，但这些属性并不意味着函数是随机预言机。随机预言机可能只有上帝世界才存在，比Hash函数限制更严格, 更困难。那只侏儒在现实中是不存在的，只存在于上帝的世界。这里的随机更像是统计学上的随机，而Hash中的随机更像是计算意义下的随机。

总结

随机预言机模型中的证明很好，但是还不够完整，无法涵盖实际的实现：我们知道，我们使用的任何函数代替随机预言机都不会是真正的随机预言机；因此，安全性依赖于强烈的希望，即现实中实际的随机函数即使不是随机预言机的部分也不会影响安全性。不过，随机预言模型中的一个证明要比根本没有证明好得多。有总比没有好吧。所有这个模型也是在理论和现实中架起了一个安全证明的桥梁。

另外提到一个题外话就是我们的链的DPoS共识基于的PVSS方案就是在DDH和ROM模型下证明安全的，还有Cardano Ada的Ouroboros也用了PVSS方案。还有现在主流PoS DPoS共识(Algorand、DFINITY)基于的Verifiable Random Function(VRF)也是依赖于ROM模型的。在论文《How to construct random functions》中也讲述了如何通过一个种子构造一个伪随机预言机。

References:

AlexiaChen avatar Jan 07 '21 03:01 AlexiaChen