Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-064 | 10th September 2001 00:00

Pseudo-Random Functions and Factoring

RSS-Feed




TR01-064
Authors: Moni Naor, Omer Reingold, Alon Rosen
Publication: 10th September 2001 16:58
Downloads: 1774
Keywords: 


Abstract:

Factoring integers is the most established problem on which
cryptographic primitives are based. This work presents an efficient
construction of {\em pseudorandom functions} whose security is based
on the intractability of factoring. In particular, we are able to
construct efficient length-preserving pseudorandom functions where
each evaluation requires only a {\em constant} number of modular
multiplications per output bit. This is substantially more efficient
than any previous construction of pseudorandom functions based on
factoring, and matches (up to a constant factor) the efficiency of
the best known factoring-based {\em pseudorandom bit generators}.



ISSN 1433-8092 | Imprint