## Going down HILL: Efficiency Improvements
for Constructions of PRG from any OWF

by Iftach Haitner, Omer Reingold and Salil Vadhan.

#### Oded's comments

The key point is the introduction of the
notion of *next bit/block pseudoentropy* (**nBPS**):
The random variable $X$ has nbPE at least $k$
if there exists a (correlated) $Y$ such that
- for all $i$ it holds that
$(X_1,...,X_{i-1},Y_i) \equiv (X_1,...,X_{i-1},X_i)$,
- $\sum_i H(Y_i|X_1,...,X_{i-1}) \geq k$.

N.B.: the nbPE may be smaller than PE; e.g.,
for a PRG $G$ consider $(G(s),s)$ for random seed $s$.
(Then PE = entropy = $|s|$, but nbPE > $|G(s)|$.)
Note this may happen only if the nbPE of $X$ is << $|X|$.
Otherwise (i.e., if nbPE = $|X|$), then PE is also $|X|$
(i.e., next bit unpredicatbility implies pseudorandomnss).
The false PE generator of HILL is thus replaced by the
following false nbPE generator, which is manipulated to obtain a PRG
(analogously but differently from the manipulation of PE in HILL).
The false nbPE generators takes input $x,h$,
where $h$ is a suitable length-preserving hashing function,
and output $f(x),h,h(x))$. This has nbPE at least $|x|+|h|+\log|x|$.
(When proving this fact,
one analyzes the first $|f(x)|+|h|+k(x)-c\log |x|$ bits via extraction,
and the next $(c+1)\log|x|$ bits via hardcore,
where $k(x)$ is $\log_2|f^{-1}(f(x))|$.)

#### The original abstract

We give a new construction of Pseudorandom Generators from any One-Way
Function. The construction achieves better parameters and is simpler
than that given in the seminal work of H.stad, Impagliazzo, Levin and
Luby [HILL 99, Haitner-Harnik-Reingold-05, Holenstein 06]. The
construction employs insights developed in the context of
constructions of statistically hiding commitments
[Haitner-Reingold-Vadhan-Wee09]. An additional advantage over all
previous constructions is that our Pseudorandom Generators invoke the
One-Way Function in a non-adaptive manner. Using
[Applebaum-Ishai-Kushilevitz04], this implies the existence of
Pseudorandom Generators in NC^0 based on the existence of One-Way
Functions in NC^1.

Back to
list of Oded's choices.