# New Pseudo-Random Generators for Weak Random Sources

### David Zuckerman

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-90-561

February 1990

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-561.pdf

We consider the following model for a weak random source: the source is asked only once for
*R* bits, and the source outputs an
*R*-bit string such that no string has probability more than 2^delta
*R* of being output, for some fixed delta > 0. We show that under the Generalized Paley Graph Conjecture, there is a pseudo-random generator that simulates RP using as a seed a string from such a source for any delta > 0. For delta > 1/2, we can simplify our generator considerably and prove its correctness without relying on any unproven assumption. Cohen and Widgerson have also solved the case delta > 1/2 using different techniques. Finally, we prove that for any delta > 0 and for all but an exponential fraction of delta-sources, an even simpler generator can simulate RP.

BibTeX citation:

@techreport{Zuckerman:CSD-90-561, Author = {Zuckerman, David}, Title = {New Pseudo-Random Generators for Weak Random Sources}, Institution = {EECS Department, University of California, Berkeley}, Year = {1990}, Month = {Feb}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/6182.html}, Number = {UCB/CSD-90-561}, Abstract = {We consider the following model for a weak random source: the source is asked only once for <i>R</i> bits, and the source outputs an <i>R</i>-bit string such that no string has probability more than 2^delta<i>R</i> of being output, for some fixed delta > 0. We show that under the Generalized Paley Graph Conjecture, there is a pseudo-random generator that simulates RP using as a seed a string from such a source for any delta > 0. For delta > 1/2, we can simplify our generator considerably and prove its correctness without relying on any unproven assumption. Cohen and Widgerson have also solved the case delta > 1/2 using different techniques. Finally, we prove that for any delta > 0 and for all but an exponential fraction of delta-sources, an even simpler generator can simulate RP.} }

EndNote citation:

%0 Report %A Zuckerman, David %T New Pseudo-Random Generators for Weak Random Sources %I EECS Department, University of California, Berkeley %D 1990 %@ UCB/CSD-90-561 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/6182.html %F Zuckerman:CSD-90-561