International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An Improved Pseudorandom Generator Based on Hardness of Factoring

Authors:
Nenad Dedic
Leonid Reyzin
Salil P. Vadhan
Download:
URL: http://eprint.iacr.org/2002/131
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2002-11654,
  title={An Improved Pseudorandom Generator Based on Hardness of Factoring},
  booktitle={IACR Eprint archive},
  keywords={foundations / pseudorandomness, pseudorandom generator, hardcore bits},
  url={http://eprint.iacr.org/2002/131},
  note={Third Conference on Seciruty in Communication Networks (SCN '02) reyzin@bu.edu 11927 received 27 Aug 2002, last revised 28 Aug 2002},
  author={Nenad Dedic and Leonid Reyzin and Salil P. Vadhan},
  year=2002
}