Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
复制标题
DOI：
10.1007/978-3-540-24638-1_2
复制
发表时间：
2004-02
期刊：
影响因子：
--
通讯作者：
U. Maurer;R. Renner;Clemens Holenstein
中科院分区：
文献类型：
--
作者：
U. Maurer;R. Renner;Clemens Holenstein
本文的目的有两个。首先，我们引入并推广了两个系统不可区分的基本概念，称为不可微性。这直接导致一个系统对另一个系统的可简化性的相关概念的推广。与传统的不可区分性概念相反，不可微性适用于假设可能的攻击者可以访问有关相关系统内部状态的附加信息的设置，例如从哈希函数族中选择成员的公共参数。其次，我们陈述了一个系统不可约（根据我们的广义定义）到另一个系统的易于验证的准则，并作为一个应用，证明了随机oracle不能约为一个较弱的原语，称为异步信标，并且异步信标不能约为有限长度的随机字符串。这些不可约性结果中的每一个都暗示了Canetti， Goldreich和Halevi的主要定理，即存在在随机预言模型中是安全的密码系统，但是用任何实现替换随机预言会导致不安全的密码系统。
The goals of this paper are two-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. In contrast to the conventional notion of indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions.Second, we state an easily verifiable criterion for a systemUnot to be reducible (according to our generalized definition) to another systemVand, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich, and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem.