Counting Unpredictable Bits: A Simple PRG from One-way Functions

Oded's comments

Paraphrasing Silvio's introduction to Leonid Levin, I'd say that the problem of simplifying the construction of PRGs based on OWFs, let alone the notion of PRGs, deserves (i.e., requires) no introduction.

The outline provided in Section 2 is quite good, and can be read while skipping most of Section 1 (with the exception of Def 1.4, or rather to be on the safe side, you may read the two paragraphs that precede it). Given the importance of this result, and pending on my schedule, I hope to post an exposition of this work asap. In the meanwhile, here is a brief outline of the four-stage construction described in Section 2.

1. The special case of regular OWFs. Given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that each image of $f$ has approximately $2^r$ preimages, we consider the function

   $$g(M,x) = (M,g'(M,x)) = (M,M(f(x)),M(x))$$
   where $M$ is an $n$-by-$n$ matrix used for hashing (i.e., $M(z)=Mz$). 
   

   Comment: It is inessential to use $M$ for operating on $f(x)$; any strong ``extraction'' that outputs $n$ bits will do. In that case, the first $2n-r-O(\log n)$ bits of $g'(M,x)$ are statistically close to a static bit-fixing source that has $n-O(\log n)$ bits (i.e., the bits in location $1,...,r-O(\log n),n+1,...,n-r-O(\log n)$).
   Recalling that the first $r-O(\log n)$ bits of $M(f(x))$ are random, the point is that (for $i\in[r-O(\log n)+1,r+O(\log n)]$), applying GL89 to the function $F'(M,x)=(M,M(f(x)),M(x)_[i-1])$ establishes that $B'(M,x)=M(x)_i$ is a hardcore preficate of $F'$. This implies that the first $n-r+O(\log n)$ bits of $M(x)$ are each unpredictable. Here it seems essential to use the specific form of $M(x)$, which guarantees that the distribution of $i$th bit of $M(x)$ depends only on the $i$th column of $M$. We stress that, $g'$ uses $n$ input bits, and extracted $n+O(\log n)$ unpredicatble bits.
   (Comment: The notion of regular OWF was introduced in GKL88.)
   
2. The same construction works in the general case, but the proof is more refined. Here we use the adaptive feature of the the definition of quantified unpredictability. The proof decouples $g$ (and its domain) into $n$ parts such that it is approximately $2^r$-to-1 on the $r$th part. Completeing the proof at this level yields a non-uniform reduction (of the security of $g$ to the security of $f$), and a uniform reduction can be obtained by using known ideas.
   The foregoing construction has (slightly) more unpredictable bits that its seed length. However, each bit location $i\in[2n]$ in the output of $g'$ is unpredictable with probability $p_i$ (ranging over the choice of $x$); we know that the sum of these $p_i$'s is at least $n+\Omega(\log n)$, but we don't know their individual values (or good lower bounds on them), whereas we will need thi information in Step 4.
3. Making the bits of $g$ invariant under shifts. We just consider $n$ (or rather $n/\log n$ if one cares about shaving a log factor) copies of $g'$ letting all use the same matrix $M$, but omit $i\in[2n]$ bits of the first copy and $2n-i$ bits of the last copy. Note that doing so comes with a loss of $2n$ bits(i.e., the omitted ones), but we can afford that since our excess is larger. Furthermore, each bit in the ooutput of the resulting function is unpredicatable with the same probability, which is $0.5+\Omega((\log n)/n)$.
4. The final randomness extraction. Denoting the function derived in Step 3 by $G$, and taking $O(n^2)$ indepedendent copies of it, we just apply a randomness extractor to each bit location in the $O(n^2)$ copies. That is, viewing the copies of $G$ as rows, we apply randomness extraction to each of the columns, where extraction is wrt min-entropy rate $0.5+\Omega((\log n)/n)$.

This work deviates from all prior works on the subject by using (next-bit) unpredictability rather than pseudorandomness (i.e., indistinguishability from random) as its pivot. Indeed, at their ``pure'' form, these notions are equivalent, but this equivalence does not seem to carry through to the relaxed forms. Specifically, pseudoentropy means being indistinguishable from a distribution of high entropy, whereas quantitative unpredictablity means that many bits (but not all) are unpredictable given the previous ones. (Indeed, both notions are quantitative and come with a suitable parameter (which quantifies how much is `high' and how much is `many').) (The notion of (next-bit) unpredictability may be viewed as a strengthening of the notion of next-block pseudoentropy (introduced by HRV13).)

A related perspective starts from the problem of randomness extraction that we face once we construct a relaxed object (i.e., either a pseudoentropy generator or quantitative unpredictablity). In the case of pseudoentropy, ``probability flattening'' is applied, and then one uses a general randomness extractor (for sources of min-entropy). In the case of quantitative unpredictablity, we face much more restricted sources, which may be viewed as an ``adaptive bit fixing source'' (of a type that differs from the one commonly considered). It stands to reason (``if there is justice in the world'' [Silvio]) that extraction from the latter type of sources is easier (once one takes a sufficient number of independent copies). Thus, repetitions are employed after quantitative unpredictablity is obtained, not towards obtaining an extractable min-entropy pseudoentropy source.

On 2nd thought (30-9-23), it is not clear that extraction is easier from this computational analogue of adaptive bit-fixing sources, because unpredictability (unlike pseodoentropy) is sensitive to the order of the bits (and holds only when one bit is read after the other).

Update (8-Oct-23): Here is the promised exposition.

The original abstract

A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically).

Our goal is to provide a construction of a PRG from OWFs with a simple proof of security; we thus focus on the setting of non-uniform security (i.e., we start off with a OWF secure against non-uniform PPT, and we aim to get a PRG secure against non-uniform PPT).

Our main result is a construction of a PRG from OWFs with a self-contained, simple, proof of security, relying only on the Goldreich-Levin Theorem (and the Chernoff bound). Although our main goal is simplicity, the construction, and a variant there-of, also improves the efficiency—in terms of invocations and seed lengths—of the state-of-the-art constructions due to [Haitner-Reingold-Vadhan, STOC’10] and [Vadhan-Zheng, STOC’12], by a factor O(log^2 n). The key novelty in our analysis is a generalization of the Blum-Micali [FOCS’82] notion of unpredictabilty—rather than requiring that every bit in the output of a function is unpredictable, we count how many unpredictable bits a function has, and we show that any OWF on n input bits (after hashing the input and the output) has n + O(log n) unpredictable output bits. Such unpredictable bits can next be “extracted” into a pseudorandom string using standard techniques.

See ECCC TR23-143.