Paper 2002/131 Original: eprint.iacr.org/2002/131 ↗
An Improved Pseudorandom Generator Based on Hardness of Factoring
Abstract
We present a simple to implement and efficient pseudorandom generator based on the factoring assumption. It outputs more than pn/2 pseudorandom bits per p exponentiations, each with the same base and an exponent shorter than n/2 bits. Our generator is based on results by Hastad, Schrift and Shamir [HSS93], but unlike their generator and its improvement by Goldreich and Rosen [GR00], it does not use hashing or extractors, and is thus simpler and somewhat more efficient. In addition, we present a general technique that can be used to speed up pseudorandom generators based on iterating one-way permutations. We construct our generator by applying this technique to results of [HSS93]. We also show how the generator given by Gennaro [Gen00] can be simply derived from results of Patel and Sundaram [PS98] using our technique.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2002-08-28: last updated
- 2002-08-28: published
- Short URL
- https://ia.cr/2002/131
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2002/131,
author = {Nenad Dedic and Leonid Reyzin and Salil Vadhan},
title = {An Improved Pseudorandom Generator Based on Hardness of Factoring},
howpublished = {Cryptology {ePrint} Archive, Paper 2002/131},
year = {2002},
url = {https://eprint.iacr.org/2002/131}
}