Paper 2001/075 Original: eprint.iacr.org/2001/075 ↗
Pseudo-Random Functions and Factoring
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)
PDF- Publication info
- Preprint.
- History
- 2001-09-10: last updated
- 2001-09-10: published
- Short URL
- https://ia.cr/2001/075
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}