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
  1. for all $i$ it holds that $(X_1,...,X_{i-1},Y_i) \equiv (X_1,...,X_{i-1},X_i)$,
  2. $\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.