Non-adaptive programmability of random oracle
Non-adaptive programmability of random oracle
复制标题
DOI：
10.1016/j.tcs.2015.05.026
复制
发表时间：
2015-08
期刊：
影响因子：
--
通讯作者：
Rishiraj Bhattacharyya;Pratyay Mukherjee
中科院分区：
文献类型：
--
作者：
Rishiraj Bhattacharyya;Pratyay Mukherjee
随机预言机是一种重要的启发式方法，用于证明许多流行和重要的密码原语的安全性。但与此同时，它们也因无法进行实际实例化而受到批评。可编程性是随机预言器强大功能背后最重要的特性之一。不幸的是，在标准哈希函数中，可编程性的特性是有限的。近年来，人们一直在努力限制随机预言机的可编程性。然而，我们观察到，现有模型允许自适应编程，即约简可以根据对手收到的查询自适应地在安全博弈的在线阶段对随机oracle进行编程，因此与标准模型相距甚远。本文引入随机预言器的非自适应可编程性，即约简算法只能在预处理阶段对随机预言器进行编程。特别是，它可能通过在oracle输出上设置一个常规函数作为后处理器来对RO进行非自适应编程。我们将这种新模型称为非自适应可编程随机Oracle (nnapo)，并证明该模型实际上等同于Fischlin等人引入的所谓非可编程随机Oracle (NPRO)，因此过于严格。然而，我们也提出了一个稍微强一点的模型，称为弱-非自适应可编程随机Oracle(WNAPRO)，其中除了非自适应编程之外，还允许从RO中自适应地提取一些“辅助信息”，这些“辅助信息”有趣地在安全证明中起着至关重要的作用，允许几个重要的RO证明通过！特别地，我们在WNAPRO模型中证明了以下结果。在WNAPRO模型中，rsa -全域哈希签名方案（RSA-FDH）和Boneh-Franklin id加密方案（BF-IDE）是安全的。这与FDH方案的强黑盒证明形成鲜明对比，在FDH方案中，完全可编程性似乎是必要的。Shoup的基于Trapdoor-permutation的密钥封装机制（TDP-KEM）不能通过对WNAPRO模型中理想Trapdoor-permutation的黑盒还原来证明其安全性。
Random Oracles serve as an important heuristic for proving security of many popular and important cryptographic primitives. But, at the same time they are criticized due to the impossibility of practical instantiation.Programmabilityis one of the most important features behind the power of Random Oracles. Unfortunately, in the standard hash functions, the feature of programmability is limited. In recent years, there have been endeavors to restrict programmability of random oracles. However, we observe that the existing models allow adaptive programming, that is, the reduction can program the random oracle adaptively in the online phase of the security game depending on the query received from the adversary, and thus are quite far from the standard model.In this paper, we introduce a new feature callednon-adaptiveprogrammability of random oracles, where the reduction can program the random oracle only in the pre-processing phase. In particular, it might non-adaptively program the RO by setting a regular function as a post-processor on the oracle output. We call this new model Non-Adaptively-Programmable Random Oracle (NAPRO) and we show that this model is actually equivalent to so-called Non-Programmable Random Oracle (NPRO) introduced by Fischlin et al. [8], hence too restrictive.However, we also propose a slightly stronger model, calledWeak-Non-Adaptively-Programmable Random Oracle(WNAPRO), where in addition to non-adaptive programming, the reduction is allowed toadaptivelyextract some “auxiliary information” from the RO and this “auxiliary information” interestingly plays crucial role in the security proof allowing several important RO proofs to go through! In particular we prove the following results in WNAPRO model.1.RSA-Full-Domain Hash signature scheme (RSA-FDH), and Boneh–Franklin ID-based encryption scheme (BF-IDE) are secure in the WNAPRO model. This is in sharp contrast to strong blackbox proofs of FDH schemes, where full programmability seems to be necessary.2.Shoup's Trapdoor-permutation based Key-encapsulation Mechanism (TDP-KEM)cannotbe proven secure via blackbox reduction from ideal trapdoor-permutations in the WNAPRO model.