An Improved Pseudorandom Generator Based on Hardness of Factoring

DSpace/Manakin Repository

An Improved Pseudorandom Generator Based on Hardness of Factoring

Citable link to this page

. . . . . .

Title: An Improved Pseudorandom Generator Based on Hardness of Factoring
Author: Reyzin, Leonid; Dedic, Nenad; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Dedic, 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.
Full Text & Related Files:
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 [PS98a] using our technique.
Published Version: http://dx.doi.org/10.1007/3-540-36413-7
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728402

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7362]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters