21
$\begingroup$

Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions:

http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf

Is there a meaningful converse? I.e., can "natural" constructions of extractors be thought of as pseudorandom generators (PRG) constructions?

Extractor constructions seem to correspond to distributions over PRGs (such that any distinguisher won't succeed in distinguishing for almost all of them). Are there known applications for this?

Improve this question
$\endgroup$
14
$\begingroup$

Salil Vadhan wrote to me that the answer to my question is known, and PRGs are equivalent to extractors.

Quoting him:

"See Proposition 21 and the discussion following it in my survey http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (There's a typo - "black-box hardness amplifier" should be "black-box PRG construction")

It says extractors are equivalent to black-box PRG constructions where you only care about the amount of advice, and not the running time, in the reduction. Asking for bounded running time amounts to asking for extractors with "local list-decoding"."

Improve this answer
$\endgroup$
0
13
$\begingroup$

This is a beautiful research question with several facets to it, and there are different ways of formalizing the question depending on whether by extractor you mean seeded extractor or seedless extractor and whether by PRG you mean PRG for Boolean circuits or a more specialized family (e.g., epsilon-biased spaces). Here's a few informal thoughts off the top of my head (but not a full answer):

  • For seeded extractors vs black-box PRGs (as in Nisan-Wigderson), it seems that black-box PRG is a stronger object than extractor. If you look at Trevisan's extractor, it's not only a polynomial-time computable extractor but has an important extra property. Namely, the analysis has a local and efficient computational element in it (namely, a local list-decoding algorithm). This extra feature is not so important for an extractor (as a combinatorial object, even if we require the extractor to be polynomial-time computable) but is crucial for a PRG (so that a distinguisher can be efficiently transformed into an algorithm for computing the hard function). In fact this can be formalized, and Ta-Shma and Zuckerman have already formalized the definition of a "black-box PRG" in their paper "Extractor Codes". They show that black-box PRGs can be used to construct extractors. For the converse, I think one can show that any extractor that satisfies the above property corresponds to a black-box PRG (in the extractor language, this would mean that the resulting extractor code must have an efficient soft-decision list-decoder). You may also find Vadhan's paper "The Unified Theory of Pseudorandomness" relevant to this discussion.

  • In the world of seedless extractors, Trevisan and Vadhan show that hard functions for a specific family of circuits result in extractors for that family (paper "Extractors for Samplable Sources"). So, for example a function that is really hard on average for AC0 can extract from sources sampled by AC0 circuits (if the min-entropy of the source is sufficiently large). Hard functions naturally relate to PRGs (as observed by Nisan-Wigderson). So here we again get a somewhat different interplay between PRGs and seedless extractors. It is however less clear how one can use an extractor for samplable sources (maybe satisfying some additional properties) to get a PRG (the next bullet point gives a partial answer to this). This direction may be less interesting than the above discussion for seeded extractors since to this date we don't have really good constructions of extractors for samplable sources.

  • From a combinatorial point of view, there is a similarity between PRGs and extractors. We can look at a PRG as a set $S$ of points in $\{0,1\}^n$ (the outcomes of the PRG for all possible seeds) or equivalently, a coloring of the $n$-dimensional hypercube in two colors. Similarly, an extractor with one bit of output (or any Boolean function, for that matter) can be seen as a set of points (those for which the extractor evaluates $0$) or coloring (in general, the number of colors would be $2^m$ where $m$ is the output length). Now, a PRG with point set $S$ fools a function with point set $F$ iff $|S \cap F|/|S|$ is close to $|F|/2^n$. Also, an extractor with point set $F$ extracts from a flat source that is uniformly distributed on a set of points $S$ iff $|S \cap F|/|S|$ is close to $1/2$. This similarity between the definitions allows one to deduce some meaningful conclusions. For example, look at an affine extractor over $\{0,1\}^n$ that extracts from min-entropy $n-1$, and outputs $1$ bit. Now consider the set $S$ of the strings that are mapped to, say, $0$ by the extractor and translate it as above to a "PRG" (with seed length $n-1$). Now the coloring interpretation above shows that the resulting function is indeed a PRG for linear functions; that is, we get an epsilon-biased generator from an extractor. This is a meaningful relationship but probably not so useful since the resulting PRG stretches the seed only by one bit. Maybe a better result can be deduced if the extractor outputs more bits, but I haven't checked that carefully.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Regarding your second point: The paper you mention gives extractors assuming hardness against classes with quantifiers. If you throw in quantifiers, AC^0 loses its meaning. (It is the same thing as NP, as was shown by Cook and Levin.) Deterministic extractors however are equivalent to sampling lower bounds, see (ccs.neu.edu/home/viola/papers/stone.pdf), where extractors for AC^0 are also obtained. $\endgroup$ – Manu Sep 11 '11 at 20:58
  • 3
    $\begingroup$ This smells like a potential blog post for the cstheory blog, if anyone might be interested :) $\endgroup$ – Suresh Venkat Sep 11 '11 at 21:01
  • $\begingroup$ Suresh: Good idea, I wasn't aware of the blog, though :) ... Emanuele: Good point. This is indeed true for samplable sources as defined by Trevisan and Vahdan. The need for quantifiers is however eliminated if you consider the dual notion of "recognizable sources". For the case of AC0, this would be the class of distributions that are uniformly distributed on zero-preimages of some AC0 circuit. Indeed you can get an extractor for sources recognized by AC0 circuits using some hard function for AC0. (continued...) $\endgroup$ – Mahdi Cheraghchi Sep 11 '11 at 22:07
  • $\begingroup$ ... However the explicit hard functions known for AC0 such as parity do not guarantee exponentially small security (advantage over random guessing) so you'd get an extractor for input entropy n(1-o(1)) if you use them directly. Better results are obtained by Shaltiel, I think, using further tricks. $\endgroup$ – Mahdi Cheraghchi Sep 11 '11 at 22:07
8
$\begingroup$

There is a nice paper of Chris Umans on the analogue of this question for dispersers: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf

He shows that dispersers that have a polynomial-time reconstruction procedure, but not necessarily the local decoding property, imply the existence of hitting set generators.

Here is another way to view it: Extractors may be viewed as list-recoverable codes (which is a stronger variant of list-decodable codes), and black-box PRGs may be viewed of local list-recoverable codes. Dispersers may be viewed as list-recoverable codes for zero-error. What Chris shows is that a list-recoverable code for zero-error that has a polynomial-time list-recovery procedure implies the existence of a list-recoverable code with local list-recovery procedure.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.