|
发表于 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。 |
|