Correcting Subverted Random Oracles
Correcting Subverted Random Oracles
复制标题
DOI：
10.1007/978-3-319-96881-0_9
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
A. Russell;Qiang Tang;M. Yung;Hong-Sheng Zhou
中科院分区：
文献类型：
--
作者：
A. Russell;Qiang Tang;M. Yung;Hong-Sheng Zhou
随机预言方法已被证明是设计和推理密码方案的强大工具，并且通常可以充当理论与实践之间的有效桥梁。在本文中，我们重点关注纠正错误的（或敌对性损坏的）随机预言的基本问题，以便它们可以自信地应用于此类加密目的。我们证明，一个简单的构造可以将“颠覆”的随机预言（在可忽略的输入部分与原始随机预言不一致）转换为与随机函数不可微分的构造。我们的结果允许未来的密码原语设计者在典型的盗窃环境中（即，对手可能会破坏密码算法的实现，但通过黑盒测试无法检测到）使用随机预言作为可信的黑匣子，尽管不信任实现。我们的分析依赖于一般拒绝重采样引理，这是一种可能具有独立利益的工具。
The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes, and can often act as an effective bridge between theory and practice. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a negligible fraction of inputs—into a construction that isindifferentiablefrom a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., with adversaries who may subvert the implementation of cryptographic algorithms but undetectable via blackbox testing) to use random oracles as a trusted black box, in spite of not trusting the implementation. Our analysis relies on a general rejection re-sampling lemma which is a tool of possible independent interest.