Certifying Trapdoor Permutations, Revisited
Certifying Trapdoor Permutations, Revisited
复制标题
重新审视证明活板门排列
DOI：
10.1007/978-3-030-03807-6_18
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Amit Lichtenberg
中科院分区：
文献类型：
--
作者：
R. Canetti;Amit Lichtenberg
陷门排列的建模已经发展了多年。事实上，找到一个适当的抽象，现有的候选结构和应用程序的需求之间的桥梁已被证明是具有挑战性的。特别是，验证排列（Bellare和Yung，96），增强和双重增强的陷门排列（Goldreich，04，08，11，Goldreich和Rothblum，13）的概念被添加到桥陷门排列和应用程序的需求之间的建模的差距差距。我们确定了一个额外的差距，在当前的抽象陷阱排列：以前的作品隐含地假设，它很容易识别域中的元素，以及统一的采样，即使是非法的函数索引。我们证明了这一差距，使用（Bitansky-Paneth-Wichs，16）双增强陷门置换家庭实例化的Feige-Lapidot-Shamir（FLS）范式构建非交互式零知识（NIZK）协议，并表明，由此产生的证明系统是不健全的。为了缩小差距，我们提出了一个一般的概念，可证明单射双增强陷门函数（DECITDFs），它提供了一种方法来证明，一个给定的密钥定义了一个单射函数定义的域，即使该域是不能有效地识别和采样。我们表明，DECITDFs足以实例化的FLS范式，更一般地说，我们认为，可证明的注入性是需要的生成过程中的功能是不可信的。然后，我们展示了两种非常不同的方法来构建DECITDF：一种是通过传统的RSA/Rabin方法与Bellare-Yung认证机制，另一种是使用不可混淆性混淆和单射伪随机生成器。特别是后者是第一个候选人内射陷门函数，从其他的假设比因子分解，这足以为FLS范式。最后，我们观察到，类似的差距也出现在文献中提出的其他路径实例化的FLS范式，特别是通过可验证的伪随机发生器和可验证的伪随机函数。缩小那里的差距可以用与这里提出的方法类似的方法来完成。
The modeling of trapdoor permutations has evolved over the years. Indeed, finding an appropriate abstraction that bridges between the existing candidate constructions and the needs of applications has proved to be challenging. In particular, the notions of certifying permutations (Bellare and Yung, 96), enhanced and doubly enhanced trapdoor permutations (Goldreich, 04, 08, 11, Goldreich and Rothblum, 13) were added to bridge the gap between the modeling of trapdoor permutations and needs of applications. We identify an additional gap in the current abstraction of trapdoor permutations: Previous works implicitly assumed that it is easy to recognize elements in the domain, as well as uniformly sample from it, even for illegitimate function indices. We demonstrate this gap by using the (Bitansky-Paneth-Wichs, 16) doubly-enhanced trapdoor permutation family to instantiate the Feige-Lapidot-Shamir (FLS) paradigm for constructing non-interactive zero-knowledge (NIZK) protocols, and show that the resulting proof system is unsound. To close the gap, we propose a general notion of certifiably injective doubly enhanced trapdoor functions (DECITDFs), which provides a way of certifying that a given key defines an injective function over the domain defined by it, even when that domain is not efficiently recognizable and sampleable. We show that DECITDFs suffice for instantiating the FLS paradigm; more generally, we argue that certifiable injectivity is needed whenever the generation process of the function is not trusted. We then show two very different ways to construct DECITDFs: One is via the traditional method of RSA/Rabin with the Bellare-Yung certification mechanism, and the other using indistinguishability obfuscation and injective pseudorandom generators. In particular the latter is the first candidate injective trapdoor function, from assumptions other than factoring, that suffices for the FLS paradigm. Finally we observe that a similar gap appears also in other paths proposed in the literature for instantiating the FLS paradigm, specifically via verifiable pseudorandom generators and verifiable pseudorandom functions. Closing the gap there can be done in similar ways to the ones proposed here.