International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Pseudo-Random Functions and Factoring

Authors:
Moni Naor
Omer Reingold
Alon Rosen
Download:
URL: http://eprint.iacr.org/2001/075
Search ePrint
Search Google
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}.
BibTeX
@misc{eprint-2001-11487,
  title={Pseudo-Random Functions and Factoring},
  booktitle={IACR Eprint archive},
  keywords={pseudo-randomness, number theory},
  url={http://eprint.iacr.org/2001/075},
  note={An extended abstract has appeared in STOC 2000. alon@wisdom.weizmann.ac.il 11575 received 10 Sep 2001},
  author={Moni Naor and Omer Reingold and Alon Rosen},
  year=2001
}