An Improved Pseudorandom Generator Based on Hardness of Factoring
MetadataShow full item record
CitationDedic, Nenad, Leonid Reyzin, and Salil Vadhan. 2003. An improved pseudorandom generator based on hardness of factoring. In Security in communication networks: Third international conference, September 11-13, 2002, Amalfi, Italy. 88-101. Berlin, Heidelberg: Springer Verlag. Lecture Notes in Computer Science, 2576: 88-101.
AbstractWe 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 [PS98a] using our technique.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4728402
- FAS Scholarly Articles