#
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