Simple extractors for all min-entropies and a new pseudorandom generatorSimple extractors for all min-entropies and a new pseudorandom generator

Access Restriction
Subscribed

 Author Shaltiel, Ronen ♦ Umans, Christopher Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Hardness versus randomness ♦ Pseudorandom generator ♦ Randomness extractor Abstract 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 $\textit{m}$ = $\textit{k}/(log$ $n)^{O(1/α)}$ and seed length (1 + α)log $\textit{n}$ for an arbitrary 0 < α ≤ 1, where $\textit{n}$ is the input length, and $\textit{k}$ 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 $\textit{not}$ based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness $\textit{directly}$ 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 $\textit{P}$ = $\textit{BPP}$ if $\textit{E}$ requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal “hitting set generator” that stretches $\textit{O}(log$ $\textit{n})$ random bits into $s^{Ω(1)}$ pseudorandom bits when given a function on log $\textit{n}$ bits that requires circuits of size $\textit{s}.$ This yields a quantitatively optimal hardness versus randomness tradeoff for both $\textit{RP}$ and $\textit{BPP}$ and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool $\textit{nondeterministic}$ circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for $\textit{AM}$ and the first hardness amplification result for nondeterministic circuits. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 52 Issue Number 2 Page Count 45 Starting Page 172 Ending Page 216

Open content in new tab

Source: ACM Digital Library