Number-theoretic constructions of efficient pseudo-random functions
Number-theoretic constructions of efficient pseudo-random functions
复制标题
DOI：
10.1145/972639.972643
复制
发表时间：
2004-03-01
影响因子：
2.5
通讯作者：
Reingold, O
中科院分区：
文献类型：
--
作者：
Naor, M;Reingold, O
我们描述了私钥和公钥密码学中各种密码原语的有效构造。我们的主要成果是两个伪随机函数的新构造。在判定版的Diffie-Hellman假设成立的情况下，证明了一种构造在Blum整数难以分解的假设下的伪随机性，而另一种构造是伪随机的。计算函数在任意给定点的值涉及两个子集积。这比以前的建议要有效得多。此外，这些函数具有在TC0（由多项式个数的阈值门组成的等深度电路可计算的函数类）中的优势。这个事实有几个有趣的应用。函数的简单代数结构暗示了额外的特征，例如对于给定伪随机函数f的键s的承诺的“y = f(s)(x)”和“y不等于f(s)(x)”形式的陈述的零知识证明。
We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that factoring (Blum integers) is hard while the other construction is pseudo-random if the decisional version of the Diffie-Hellman assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC0 (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form "y = f(s)(x)" and "y not equal f(s)(x)" given a commitment to a key s of a pseudo-random function f.