Number-theoretic constructions of efficient pseudo-random functions
Number-theoretic constructions of efficient pseudo-random functions
复制标题
DOI：
10.1109/sfcs.1997.646134
复制
发表时间：
1997-10
期刊：
影响因子：
--
通讯作者：
M. Naor;Omer Reingold
中科院分区：
文献类型：
--
作者：
M. Naor;Omer Reingold
我们描述了各种密码原语（在私钥和公钥密码）的有效结构。我们表明，这些结构至少是安全的Diffie-Hellman假设的决策版本或作为假设，分解是困难的。我们的主要结果是一个新的伪随机函数的建设，使计算其值在任何给定的点涉及两个多个产品。这比以前的建议要有效得多。此外，这些功能的优势是在TC/sup 0/（一类功能可计算的常数深度电路组成的多项式数量的阈值门），这有几个有趣的应用。简单的代数结构的功能意味着额外的功能。特别是，我们展示了一个零知识证明的陈述形式“y=f/sub s/（x）”和“y/spl ne/f（x）”给定一个承诺的关键s的伪随机函数f/sub s/。
We describe efficient constructions for various cryptographic primitives (both in private-key and in public-key cryptography). We show these constructions to be at least as secure as the decisional version of the Diffie-Hellman assumption or as the assumption that factoring is hard. Our major result is a new construction of pseudo-random functions such that computing their value at any given point involves two multiple products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC/sup 0/ (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates) which has several interesting applications. The simple algebraic structure of the functions implies additional features. In particular, we show a zero-knowledge proof for statements of the form "y=f/sub s/(x)" and "y/spl ne/f(x)" given a commitment to a key s of a pseudo-random function f/sub s/.