Simple extractors for all min-entropies and a new pseudorandom generator
Ronen Shaltiel, Christopher Umans
Journal of the ACM·2005·97 citations
<jats:p>
A “randomness extractor” is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure of the amount of randomness in a distribution.) We present a simple, self-contained extractor construction that produces good extractors for all min-entropies. Our construction is algebraic and builds on a new polynomial-based approach introduced by Ta-Shma et al. [2001b]. Using our improvements, we obtain, for example, an extractor with output length
<jats:italic>m</jats:italic>
=
<jats:italic>k</jats:italic>
/(log
<jats:italic>n</jats:italic>
)
<jats:sup>
<jats:italic>O</jats:italic>
(1/α)
</jats:sup>
and seed length (1 + α)log
<jats:italic>n</jats:italic>
for an arbitrary 0 < α ≤ 1, where
<jats:italic>n</jats:italic>
is the input length, and
<jats:italic>k</jats:italic>
is the min-entropy of the input distribution.A “pseudorandom generator” is an algorithm that given a short random seed produces a long output that is computationally indistinguishable from uniform. Our technique also gives a new way to construct pseudorandom generators from functions that require large circuits. Our pseudorandom generator construction is
<jats:italic>not</jats:italic>
based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness
<jats:italic>directly</jats:italic>
into pseudorandomness. The parameters of our generator match those in Impagliazzo and Wigderson [1997] and Sudan et al. [2001] and in particular are strong enough to obtain a new proof that
<jats:italic>P</jats:italic>
=
<jats:italic>BPP</jats:italic>
if
<jats:italic>E</jats:italic>
requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal “hitting set generator” that stretches
<jats:italic>O</jats:italic>
(log
<jats:italic>n</jats:italic>
) random bits into
<jats:italic>s</jats:italic>
<jats:sup>Ω(1)</jats:sup>
pseudorandom bits when given a function on log
<jats:italic>n</jats:italic>
bits that requires circuits of size
<jats:italic>s</jats:italic>
. This yields a quantitatively optimal hardness versus randomness tradeoff for both
<jats:italic>RP</jats:italic>
and
<jats:italic>BPP</jats:italic>
and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool
<jats:italic>nondeterministic</jats:italic>
circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for
<jats:italic>AM</jats:italic>
and the first hardness amplification result for nondeterministic circuits.
</jats:p>