Paper 2001/075

Pseudo-Random Functions and Factoring

Moni Naor, 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}.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. An extended abstract has appeared in STOC 2000.
Keywords
pseudo-randomnessnumber theory
Contact author(s)
alon @ wisdom weizmann ac il
History
2001-09-10: received
Short URL
https://ia.cr/2001/075
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/075,
      author = {Moni Naor and Omer Reingold and Alon Rosen},
      title = {Pseudo-Random Functions and Factoring},
      howpublished = {Cryptology {ePrint} Archive, Paper 2001/075},
      year = {2001},
      url = {https://eprint.iacr.org/2001/075}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.