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.