Cryptology ePrint Archive: Report 2001/075

Pseudo-Random Functions and Factoring

Moni Naor and Omer Reingold and Alon Rosen

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}.

Category / Keywords: pseudo-randomness, number theory

Publication Info: An extended abstract has appeared in STOC 2000.

Date: received 10 Sep 2001

Contact author: alon at wisdom weizmann ac il

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20010910:174450 (All versions of this report)

Short URL: ia.cr/2001/075

Discussion forum: Show discussion | Start new discussion