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

by Iftach Haitner, Omer Reingold and Salil Vadhan.

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.