Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-064 | 10th September 2001 00:00

#### Pseudo-Random Functions and Factoring

TR01-064
Authors: Moni Naor, Omer Reingold, Alon Rosen
Publication: 10th September 2001 16:58
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