You are looking at a specific version 20010910:174450 of this paper.
See the latest version.
Paper 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}.
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
-
CC BY