Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-045 | 4th September 1995 00:00

Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions

RSS-Feed




TR95-045
Authors: Moni Naor, Omer Reingold
Publication: 20th September 1995 13:31
Downloads: 1242
Keywords: 


Abstract:

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 an $NC^1$ implementation of synthesizers based on
the RSA or the Diffie-Hellman assumptions.
This yields the first parallel pseudo-random function
and the only alternative
to the original construction of Goldreich, Goldwasser
and Micali.
The security of our constructions is similar to the
security of the underling assumptions.
The connection with problems in Computational Learning Theory is discussed.



ISSN 1433-8092 | Imprint