请选择 进入手机版 | 继续访问电脑版

混凝土搅拌站故障及解决方案

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 940|回复: 2

究竟什么才是随机预言机(random oracle)呢?

[复制链接]

24

主题

35

帖子

113

积分

注册会员

Rank: 2

积分
113
发表于 2018-10-31 13:54:01 | 显示全部楼层 |阅读模式
维基百科:在密码学里面,随机预言是一个预言(简单说像是理论的黑箱),对任何输入都回传一个真正均匀随机的输出(请参考离散型均匀分布),不过对相同的输入,该预言每次都会回传一模一样的输出。换句话说,随机预言是一个将所有可能输入与输出作随机映射的函数。  可是既然说对于输入给出是随机输出,那又为什么会是对相同的输入,该预言每次都会回传一模一样的输出呢?
回复

使用道具 举报

15

主题

26

帖子

111

积分

注册会员

Rank: 2

积分
111
发表于 2018-10-31 13:35:44 | 显示全部楼层
和  已经介绍了 RO 的定义,我就不多重复。这里重点说说 RO 的用处。

Random Oracle 是密码学中 (Keyed) Pseudorandom Function,缩写 PRF,的抽象。PRF 是一个函数 ,其中 Key Space K 一般取 ,X,Y 可以相同可以不同,不妨令 。f 是 PRF 当且仅当对于随机选取的 key k, 和随机选取的函数 在 Oracle access 下 Computationally indistinguishable.

应该可以注意到 PRF 和 RO 的惊人相似性。如果不知道 k,且只能询问 的值。那 PRF 和 RO 是(Computationally)一样的。这时攻击者几乎无能为力,因为在不同输入下的输出是 i.i.d. uniform,攻击者不可能从中找到任何机会。攻击者不可能做到的事情包括:预测下一个输出,求逆,寻找碰撞 etc

但是问题来了:如果只能 Oracle access,就意味着每次想知道 PRF 在某个输入下的值 ,都要询问一次。这样的系统几乎不可能是实用的。实用体系需要每一方都可以自行计算 PRF。因此 PRF 的某一部分,总是要暴露给攻击者的。
密码学界对此的回应。。。。。暂时把问题扫的地毯下面。。。假设有某种神奇的方式,可以允许攻击者自行计算 PRF,又不给于其任何其它的帮助。

一种想法是把 PRF 包装起来,比如用 Obfuscation,将计算 PRF 的程序混淆后再发给潜在的攻击者。如果 Virtual Black Box (VBB) Obfuscation 可以实现,那这个问题就解决了,PRF 都可以用 RO 来 model。但现实往往是残酷的 T_T。VBB、RO 等已经被证明是无法实现的 [这里应该有点引用]。

比如一个简单的“例子”,只用来建立直觉。假设我收到了一个被 VBB Obfuscate 的 PRF,看看有什么事情我在 RO 模型下不能做但现在能做的。在 RO 模型下,我无法简洁的描述这个函数,因为在我看来这个函数和随机差不多(Computationally indistinguishable),而随机函数需要指数长度的描述。但我拿到了 VBB Obfuscated PRF circuit 之后,这就是一个简洁描述呀!Done.  
当然能做这种程度的事情还不很厉害,人家原 paper 还有做更厉害的事情。

由于这个问题,大家对 RO model 的热情其实有限。同样遭遇的还有 RP (Random Permutation) model。如果证明使用了这些模型,会被认为提供了一些洞察/证据,但不够 solid。

[这里应该有点引用] 听 Amit 说的,所以没有引用。好在评论区里有人  补充了工作。
回复

使用道具 举报

19

主题

26

帖子

90

积分

注册会员

Rank: 2

积分
90
发表于 2018-10-31 14:35:43 | 显示全部楼层
首先吐个槽:
英文维基这个词条明明是给了随机预言机(random oracle,简称RO)两个大大不同的理解,偏偏只用了一个“Stated differently”(换句话说),而且中文维基还有翻译问题.

当然,两个理解都是正确的,下面我来解释。

理解一
在里面,随机预言是一个(简单说像是理论的),对任何输入都回传一个真正均匀的输出(请参考),不过对相同的输入,该预言每次都会回传一模一样的输出

In , a random oracle is an  (a theoretical ) that responds to every unique query with a (truly)  response chosen  from its output domain. If a query is repeated it responds the same way every time that query is submitted.
对比中英文下划线部分,应该发现问题了吧。“repeated” 是指“重复出现的”,而不是“相同的”。
这种理解,其实代表下面这个通过与访问者互动来确定RO状态的过程。(interactive process)

符号O(x)指RO对于输入x的输出, L代表O(x)的长度。(L是安全参数n的函数)

1. RO一开始维护一张空表,表有两列,一列是输入,一列是输出
2. 如果访问者第一次的输入为x, 则RO均匀随机从中选一个值O(x), 把x记录在表里。

3. 对于第二个以及之后的访问y,如果y没有在输入这一列出现,则RO均匀随机从选出O(y), 反之,即y出现过,则把输出这一列中,y对应的O(y)再次输出。
这也就是“真正均匀随机”和“对重复值输出相同”的意思。

理解二
换句话说,随机预言是一个将所有可能输入与输出作随机映射的


Stated differently, a random oracle is a random , that is, a function mapping each possible query to a (fixed) random response from its output domain.
翻译又把(fixed)给扔了,这个至关重要。
此理解是说,在访问者发起第一个问题前,RO的状态就是以某种方式确定的了
这个某种方式就是指,从所有的输入范围为所有01字符串,输出长度为L的函数集合中,均匀随机的选定一个函数F,作为此次RO的状态。随后,以F的方式来回应访问者。L是安全参数n的函数。

看看Ran Canetti, Oded Goldreich, Shai Halevi三位大家在The Random Oracle Methodology, Revisited这篇论文里对RO的描述吧,就是上述的理解

It is postulated that all oracle queries, regardless of the identity of the party making
them, are answered by a single function, denoted O, that is uniformly selected among all possible functions. The set of possible functions is determined by a length function and by the security parameter of the system.
题外话,一个RO通常被当作安全的Hash函数,但通常只能在一次证明中使用,就是说,你不能拿着已经确定状态、并且已知部分输入输出关系的RO放入另一个证明里。新证明最好用“空白”的RO。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|中国机械问答网 ( 粤ICP备15029207号 )|网站地图

GMT+8, 2024-3-28 18:34 , Processed in 0.104857 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表