You are looking at a specific version 20020828:202215 of this paper. See the latest version.

Paper 2002/131

An Improved Pseudorandom Generator Based on Hardness of Factoring

Nenad Dedic and Leonid Reyzin and Salil Vadhan

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 PS
Category
Foundations
Publication info
Published elsewhere. Third Conference on Seciruty in Communication Networks (SCN '02)
Keywords
pseudorandomnesspseudorandom generatorhardcore bits
Contact author(s)
reyzin @ bu edu
History
2002-08-28: revised
2002-08-28: received
See all versions
Short URL
https://ia.cr/2002/131
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.