Synthesizers and Their Application to the Parallel Construction
of Pseudo-Random Functions
Moni Naor and Omer Reingold
The Weizmann Institute of Science, Rehovot, Israel.
A pseudo-random function is a fundamental cryptographic primitive that
is essential for encryption, identification and authentication. We present
a new cryptographic primitive called pseudo-random synthesizer and show
how to use it in order to get a parallel construction of a pseudo-random
function. We show several NC^1 implementations of synthesizers based on
concrete intractability assumptions as factoring and the Diffie-Hellman
assumption. This yields the first parallel pseudo-random functions (based
on standard intractability assumptions) and the only alternative to the
original construction of Goldreich, Goldwasser and Micali. In addition,
we show parallel constructions of synthesizers based on other primitives
such as weak pseudo-random functions or trapdoor one-way permutations.
The security of all our constructions is similar to the security of the
underlying assumptions. The connection with problems in Computational Learning
Theory is discussed.
, gzipped Postscript .
Back to On-Line Publications