NOV 2011 -- ADDITIONAL COMMENTS REGARDING CHOICE NR 63
("Pseudorandom Generators with Long Stretch 
 and Low Locality from Random Local One-Way Functions" by Benny Applebaum).


Recall

OWF == one-way function == functions that are easy to compute
       but hard to invert (on typical images). 

PRG == pseudorandom generators == efficient algorithms that stretch 
       $n$-bit bit long seeds into $m$-bit long sequences that
       are computationally indistinguishable from random $m$-bit strings.
       
Note that the stretch of a PRG can be 
either sub-linear (i.e., $m-n = o(n)$),
or linear (i.e., $m-n = Omega(n)$), 
or polynomial (i.e., $m > n^{1+Omega(1)}$). 
Let's use the terms slPRG, LPRG, and PPRG. 

Wrt the basic definition (i.e., efficient == poly-time), 
it is known that slPRG implies PPRG,
but this paper deals with *extremely efficient* PRGs;
those computable in NC0 (i.e., each output depends on $O(1)$ input bits).
In the latter setting, there is a HUGE gap between what is known
about slPRGs and LPRGs (let alone PPRGs):
* Under standard assumptions (e.g., factoring),
  there exists slPRGs computable in NC0.
* Nothing is known wrt LPRGs.

When I say "nothing is known", I mean nothing beyond
presenting a candidate construction and conjecturing that it is a PRG.

The point is that NOT all assumptions are *equal*.
A key aspect of modern cryptography refers to this *inequality*;
a major concern of this field is reducing assumptions,
that is, reducing strong/complex assumptions (like PRG) 
into weaker/simpler ones (like OWF). 

Indeed, saying that a function is hard to invert
is fundamentally simpler and weaker than saying 
that applying a function to the uniform distribution
yields a distribution that is hard to distinguish
from the uniform one. 

Getting back to the state of PRGs computable in NC0,
what we currently have is
* Assumptions of the OWF type (i.e., factoring)
  are known to imply the existence of slPRGs computable in NC0.
* No OWF-type assumption is known to imply LPRG computable in NC0.

So what this paper does is show that:
1. A OWF-type assumption implies LPRG computable in NC0. [Thm 1.2]
2. A OWF-type assumption "almost implies" PPRG computable in NC0. [Thm 1.3]
   (This "almost implies" comes in two alternative flavors -- see below.) 
Yes, it would have been nice to replace "almost implies" by "implies",
and this is indeed the main challenge left open for future work!

(The introduction provides some concere reasons to why we should care 
about LPRGs and PPRGs computable in NC0. I don't need such things
in order to recognize a fundamental question when I see it.) 

I think that the exposition does injustice to the proof of Thm 1.2.
It does not provide a good sketch of the underlying construction 
(i.e., one that may be useful for the reader); 
but rather goes into a private discussion with the authors of HRV+AIK, 
telling them what wonderful things are implicit in their work etc. 
A reader other than these authors 
(and a handful of other knowledgeable experts) 
may have no clue what is going on in this private discussion. 
Since I know, let me tell you a secret: 
something very interesting is going on
(i.e., a weak next-bit unpredictable generator is constructed,
and a PRG is obtained by combining it with an *NC0-computable* 
randomness extractor with weak parameters (which suffices here,
and is also of *independent* interest) to get a PRG). 
[So HRV+AIK+X+Y+Z could have figured it out 
(*if* you'd ask them the right question!), 
but the issue is serving a wider community.] 

Another contribution of this work is that it makes significant
progress in the study of Goldreich's candidate OWF, which is
closely realted to the OWF-type assumptions used in Thm 1.2 and 1.3.
Specifically, Thm 1.4 states that if that function is a OWF,
then its projection (on fewer output bits) is a "weak PRG",
which is one of the two alterantives that make Thm 1.3 an "almost".

Tech details -- the two flavors of THM 1.3.
2a. A OWF-type assumption implies PPRG in which each output bit
    depends ohn $log^* n$ bits rather than O(1) bits.
2b. A OWF-type assumption implies a weak-PPRG computable in NC0,
    where a weak-PRG is one for which no PPT algorithm can
    distinguish the generator's output from a random $m$-bit string
    with probability greater than $1/m^3$ (rather than with probability
    that vanishes faster than any reciprocal of a polynomial in $m$).
    Needless to say, 3 can be replaced by any *fixed* constant;
    the point is that for every polynomail there is a generator
    (rather than a single generators that beats all polynomials).