Number-Theoretic Constructions of Efficient Pseudo-Random Functions

Moni Naor and Omer Reingold

Abstract:

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^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_s(x)'' and ``y neq f_s(x)'' given a commitment to a key, s, of a pseudo-random function f_s.

Postscript , gzipped Postscript .
Implementation (Mike Langberg)
 

Related Online Papers

  • Moni Naor, Benny Pinkas and Omer Reingold, Distributed Pseudo-Random Functions and KDC. Eurocrypt'99. Abstract, Postscript , gzipped Postscript .
  • Moni Naor and Omer Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions. J. of Computer and Systems Sciences, vol. 58 (2), April 1999, pp. 336-375.  Abstract, Postscript , gzipped Postscript.
  • Moni Naor and Omer Reingold, From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs, Crypto'98. Abstract, Postscript, gzipped Postscript .
  • Moni Naor, Omer Reingold and Alon Rosen, Pseudo-Random Functions and Factoring, SIAM J. Computing, vol 31(5), 2002, pp. 1383--1404, (STOC 2000), Abstract, Postscript, gzipped Postscript


    • Back to On-Line Publications

    Back Home