ECCC-Report TR01-064https://eccc.weizmann.ac.il/report/2001/064Comments and Revisions published for TR01-064en-usMon, 10 Sep 2001 16:58:17 +0300
Paper TR01-064
| Pseudo-Random Functions and Factoring |
Moni Naor,
Omer Reingold,
Alon Rosen
https://eccc.weizmann.ac.il/report/2001/064Factoring 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}.
Mon, 10 Sep 2001 16:58:17 +0300https://eccc.weizmann.ac.il/report/2001/064