PRG from any OWF

We assume that the OWF f:{0,1}n{0,1}n. This is w.l.o.g.: if input is shorter, then we pad the input with unused random bits; if the output is shorter, then we pad the output with fixed bits. The same applies to the new notions in this section, namely weak PEG and PEG.

Historically, the first construction of PRG from OWF is given by HILL’99, which was initiated by IL’89 and ILL’89. The construction here is presented by a lecture of Barak at Princeton, which followed the paper of Holenstein’06. Later, HRV’13 and VZ’12 improved the efficiency. Interestingly in constructions of PRG, there are several novel tools that are useful later, e.g., the Leftover Hash Lemma, due to [ILL’89].

Even the result is impactful, the full construction is often skipped in textbooks and graduate-level cryptography. Many books and courses cover the Goldreich-Levin hard-core lemma [Ps, KL], but only few of them goes beyond that (such as the lecture of Bellare, 1999). The book of Goldreich, Section 3.5 is one that goes much deeper, which constructs PRG from any “regular” OWF, where regular means that for the same length x, the pre-image set f1(f(x)) is the same cardinality. Still, the full construction

… is even more complex and is not suitable for a book of this nature.

Goldreich, Section 3.5

The only teaching material we found is the lecture of Barak.

We will use pairwise independent hash functions. The following facts are borrowed from the book of Salil Vadhan, Pseudorandomness, cited as [V].

Definition: Pairwise independent hash family.

A family of functions H={h:{0,1}n{0,1}m} is pairwise independent if the following two conditions hold when hH is a function chosen uniformly at random from H:

  1. For all x{0,1}n, the random variable h(x) is uniform in {0,1}m.
  2. For all x1x2{0,1}n, the random variables h(x1) and h(x2) are independent.

[V, Definition 3.21, p64]

Lemma: Pairwise independent hash from linear mapping.

For any finite field F, define H to be the following set:

H:={ha,b:ha,b(x)=ax+b,a,bF}.

H is a pairwise independent hash family. We often abuse notation, denoting hH to be the seed and h(x) to be the evaluation of the hash function.

[V, Construction 3.23, p65]

If mn, choosing the field to be F2m gives a construction such that each function takes 2m bits to describe. If m<n, choosing F2n and chopping the output to m bits is still pairwise independent.

Corollary:

For any n,mN, there exists a pairwise independent hash family Hn,m such that each hH is 2max(n,m) bits.

[V, Theorem 3.26, p66]

Definition: statistical difference

For random variables X and Y taking values in U, their statistical difference (also known as variation distance) is Δ(X,Y):=maxTU|Pr[XT]Pr[YT]|. We say that X and Y are ϵ-close if Δ(X,Y)ϵ.

[V, Definition 6.2, p169]

Fact:

For any nN, ϵ0 and random variable X, if X is ϵ-close to Un, then Pr[yUn:ySupp(X)]1ϵ, where Supp(X):={x:Pr[X=x]>0} denotes the support of X.

Definition: entropy measures

Let X be a random variable. Then

  • the Shannon entropy of X is:

    H(X)=ExX[log1Pr[X=x]].
  • the min-entropy of X is:

    H(X)=minx{log1Pr[X=x]}.

where all logs are base 2.

[V, Definition 6.7, p171]

Definition: k-source

A random variable X is a k-source if H(X)k, i.e., if Pr[X=x]2k.

[V, Definition 6.9, p173]

Definition: (k,ϵ)-extractor

A function Ext:{0,1}n×{0,1}d{0,1}m is a (k,ϵ)-extractor if for every k-source X on {0,1}n, Ext(X,Ud) is ϵ-close to Um.

[V, Definition 6.13, p176]

Theorem: Leftover Hash Lemma

If H={h:{0,1}n{0,1}m} is a pairwise independent family of hash functions where m=k2log(1/ϵ), then Ext(x,h)=(h,h(x)) is a standard (k,ϵ)-extractor.

[V, Theorem 6.18, p179]

Corollary: Guessing the hash value

Let H be a pairwise independent hash family, from n-bit strings to n-bit strings. For any random variable X{0,1}n such that H(X)=kn,

Pr[hH,yUkd:xSupp(X),hkd(x)=y]12d/2

where ht(x) denotes the prefix t bits of h(x).

Weak Pseudo-Entropy Generator (PEG)

The first step, a gap in Shannon entropy and pseudo-entropy.

Definition: weak PEG

A function F:{0,1}n{0,1}m is called a weak pseudo-entropy generator(PEG), if there exists a k such that

  1. There exists Yn such that {F(Un)}n{Yn}n and H(Yn)k+1100n. (This is called pseudo Shannon entropy.)
  2. H(F(Un))k.

Discuss Is a weak PEG also a weak OWF?

Theorem: Weak PEG from OWF

Let f:{0,1}n{0,1}n for all nN be a OWF, let H be a pairwise independent hash family that for each hH, h:{0,1}n{0,1}n and |h|=2n. Define function f to be the following:

F(x,i,h,r):=(f(x),i,h,hi(x),r,xr), and 

where h is abused to denote the description of hH, hi(x) denotes the i-bit prefix of h(x). Then, f is a weak PEG.

Intuition for the construct:

  • f(x),r,xr is GL hardcore lemma, the starting point to obtain a pseudo-random bit (i.e., pseudo-entropy). However, xr gives no extra pseudo-entropy for many-to-one f.
  • f(x),r,x,h(x) is attempting to obtain PE by “identifying different” xf1(f(x)) through h(x). However, by randomizing h, any x may map to h(x) (like OTP), bad identification.
  • f(x),r,x,h,h(x) is giving h, and we get good identification. However, too good to be easy to invert x since solving h(x)=ax+b is easy.
  • f(x),r,x,h,hi(x),i is cutting h(x) short to make inverting hard. For proper choice of i(x), this works, but i(x) is hard to compute.
  • We end up with guessing random i. It works, the proof follows below.

For each x{0,1}n, let i(x):=log|f1(f(x))|+1. Let i to be i(x) and Z to be Zi(x) for short. Let random variables Y,Z,Zi be the following

Y:=(f(x),i,h,hi(x),r), Z:=xr, and Z:={random bitif i=ixrotherwise.

Claim: Low Shannon entropy

H(YZ)H(YZ)+12n

We have H(YX)=H(Y)+H(X|Y) for all X,Y (proof left as exercise). Hence, it suffices to show that H(Z|Y)H(Z|Y)+12n. Conditioned on ii, we have H(Z|Y)=H(Z|Y). We want to show that when conditioned on i=i, H(Z|Y)=1H(Z|Y)+12, which happens w.p. 1/n. It remains to show that H(Z|Y)1/2. We will show that given (f(x),i,h,hi(x),r), w.h.p. it holds that x is uniquely determined, and thus Z=xr is also determined (and gives 0 Shannon entropy).

For any x{0,1}n and yf(x), define the pre-image set S:=f1(f(x)){x}. Notice that |S|2i1. By h is pairwise independent, for any xS,

Prh[hi(x)=hi(x)]=1/2i.

To see x is determined over the random h,

Prh[xS s.t. h(x)=h(x)]=1Pr[xS s.t. h(x)=h(x)]1|S|/2i1/2,

by union bound and then by |S| is small.

(The calculation of conditional entropy is left as exercise.)

Claim: High pseudo-entropy

{YZ}n{YZi(x)}n.

Proof Sketch.

Because YZ,YZ differ only when i=i, assume for contradiction, there exists NUPPT A, polynomial p, such that for inf many n,

Prx,h,r[A(f(x),i,h,hi(x),r)=xr]1/2+α,

where α=1/p(n).

We want to construct B that inverts yf(x). We have a similar claim of good x’s: let G to be the set

G:={x{0,1}n | Prh,r[A(f(x),i,h,hi(x),r)=xr]1/2+α/2}.

Then, |G|2nα/2. We can next fix h similarly: for each xG, let Gx to be the set

Hx:={hH | Prr[A(f(x),i,h,hi(x),r)=xr]1/2+β}.

Then, |Hx||H|β, where β:=α/4.

Now, we can condition on xG and hHx. Namely, given yf(x), B tries all i[n] and samples hH uniformly, and we have that i=i and hHx w.p. β. It remains to find the correct h(x) so that B can run A repeatedly using pairwise independent r’s.

Suppose that x is fixed and h is sampled uniformly and independently from H. Given y=f(x), the min-entropy of x is i(x)1 because each xf1(y) can be mapped to y. By the corollary of Leftover Hash Lemma, “guessing the hash value”, the first id bits of h(x) is 2(d1)/2-close to uniform. This implies that we can hit the first id bits of hi(x) w.p. 12(d1)/2 by sampling them uniformly at random.

However, to apply A, we also conditioned on hHx (instead of uniform h). Hence, we need to take union bound:

  • hHx w.p. 1β
  • the guess is not the first id bits of h(x) for all xf1(y) w.p. 2(d1)/2.

Thus, choosing d such that 2(d1)/2β/2, we will sample a “good” input (y=f(x),i,h,hi) to A w.p. β/2 (only conditioned on xG). With the above, we can try all remaining d=O(2logβ)=O(logn) bits and then check if the outcome x satisfies f(x)=y.

Algorithm B(y):

  1. hH
  2. d:=log(α/4)+1
  3. For each i=1,,n,
    1. t1{0,1}id
    2. For each t2{0,1}d,
      • Let t:=t1t2.
      • Run xB0(y,i,h,t).
      • Output x if f(x)=y.

The subroutine B0 performs almost identical to the standard Goldreich-Levin, and the only difference is that A takes additional input (i,h,hi).

Algorithm B0(y,i,h,hi)

  1. Let :=logm, (u1,,u) be fully independent and (r1,,rm) be pairwise independent n-bit random strings.
  2. For each k[], sample guess bit bk uniformly. For each j[m], compute the bit gi,j from (b1,,b) in the same way as rj (so that for any x, gi,j=xrj and bk=xuk for all k).
  3. For each i=1,2,..,n,
    1. For each j=1,2,,m,
      • Run zi,jA(y,i,h,hi,eirj)gi,j.
    2. Let xi be the majority of {zi,j}j[m]
  4. Output x:=x1x2xn

The parameter m is choosen according to the success probability of A conditioned on xG and hHx and (i,hi) are consistent. Notice that conditioned on xG, the events hHx and t1 hits hi(x) are independent, w.p. β and 1/2. Also, B runs over all possible i and t2. Hence, the overall success probability is poly(1/n,1/p(n)).

Discuss Is F a OWF? No, consider the case i=n, which happens w.p. 1/n, and then w.h.p. over h, we can solve x from (h,hi(x)). However, the above claim also showed that F is hard to invert when i=i(x), i.e., F is a weak OWF.

PEG from Weak PEG

Definition: Pseudo-entropy generator (PEG)

A function g:{0,1}n{0,1}n is called a pseudo-entropy generator(PEG), if there exists a k such that

  1. There exists Yn such that {g(Un)}n{Yn}n and H(Yn)k+nα for some constant α>0. (This is called pseudo min-entropy.)
  2. H(g(Un))k(1±β(n)) with probability 1ϵ(n) for negligible ϵ and small fraction β(n)0.1nα1. More precisely, there is a Yg(Un) such that Prx[g(x)Y]1ϵ(n) and that for all aY, Prx[g(x)=a]2k(1±β).

Notice that compared to weak PEG, here for PEG, we require that the entropy gap to be min-entropy (instead of Shannon entropy) and that the entropy gap to be much more than constant bits.

Theorem: PEG from Weak PEG

Suppose F:{0,1}n{0,1}n is a weak PEG. Let g:{0,1}n{0,1}n to be the function

g(x1...x):=F(x1)...F(x),

where xi{0,1}n for all i, and :=(n) is a polynomial (to be chosen later). Then, g is a PEG.

Discuss The construction of g is identical to that from weak OWF to strong OWF. Also recall that the weak PEG is also a weak OWF.

Let k be the Shannon entropy of F(Un). Observe that:

  • The min-entropy H(F(Un)) can be k (which is not good for our purpose); that means
  • There exists bad a such that Prx[F(x)=a]1/2k; however,
  • All such a can not take much probability mass over all F(Un) (otherwise, the Shannon entropy would be <k).

Therefore, since we repeat F independently for instances, those bad a can only happen in a small fraction of with non-negligible probability. Namely,

  • The Shannon entropy of g(Un) is k.
  • Most of F(Un) instances in g(Un) are good,
  • Each good gives min-entropy close to k, and thus
  • it gives total min-entropy close to k, upto a small fraction.

This is called entropy equalization in [HRV13]. Notice that the argument is two-sided. It is formalized in the following and proved by Chernoff bound.

Claim: Low min-entropy

Let S:=Supp(g(x1x)) be the support of g. Define T to be the set

T:={yS|Pr[g(x1...x)=y]2k(1±β)},

where the probability is over x1x that are sampled uniformly, and β>0. Then

Prx[g(x)T]2Ω(β2k/n).

This implies that H(g(Un))k(1+β) for all but 2Ω(n) fraction of x’s.

In general, min-entropy is less than the Shannon entropy of the same variable. Here, we want to show the opposite by relaxing a β fraction in entropy and by skipping a small fraction of y’s.

The idea is that repeating F for (n) times independently “smooths” the overall distribution. Because H(F(Un))=k is an average notion, a majority of ySupp(F(Un)) satisfy that Pr[F(Un)=y]2k(1±β), where the majority is measured in probability mass. Repeating independently, the majority is further concentrated to an overwhelming probability mass by Chernoff bound of the following form.

Chernoff’s Inequality (For Real Random Variables)

Let X1X be independent random variables taking real value in [0,n], let X:=i[]Xi, and let μ:=E[X]. For any 0<δ<1,

Pr[|Xμ|δμ]2eμδ2/3n.

The calculation is as follows. For any y{0,1}m, define γ(y):=Pr[F(Un)=y].

Pry=(y1...y)g(x)[Prz[g(z)=y]2k(1±β)]=Pry[i[]γ(yi)2k(1±β)]=Pry[i[]logγ(yi)k(1±β)]=Pry[|i[]Xik|±βk]2Ω(β2k/n),

where Xi:=logγ(yi) by definition, and E[Xi]=H(F(Un))=k by definition of Shannon entropy and weak PEG.

Claim: High pseudo-min-entropy

Let Y be the distribution such that is indistinguishable from F(Un) but H(Y)k+1100n. There exists a distribution Y such that Hk(1β)+nα and that Y is indistinguishable from g(x), where α>0 is a constant.

Proof sketch.

By a non-uniform reduction, g(Un) is indistinguishable from Z:=Y1Y such that Y1,Y2,,Y are sampled from Y independently (* see caviate below). We have Shannon entropy H(Z)k+/100n, but we want Y with high min-entropy. By a Chernoff bound that is similar to the previous claim, we have that for all except for exponentially small probability,

PryZ[γ(y)2(k+/100n)(1±β)]2Ω(β2/n),

where γ(y):=PryZ[y=y] for all y. We simply get rid of those “bad y” from Z and obtain the distribution Y by moving the probability mass 2Ω(β2/n) to all strings in {0,1}m uniformly, which yields Y with min-entropy at most

log(2(k+1/100n)(1β)+2n2Ω(β2/n))

which is at least (k+Ω(/n))(1β)2Ω(β2/n) because ln(1+x)x as x0 by Taylor series. Choosing β(n):=0.01/n2 and (n)=n9, we have the gap at least (n)8/10o(1) (and thus α=0.8, we can choose even smaller β and larger ).

Notice that the entropy gap is roughly Ω(/n)2βk, which incurs a huge .

* Caviate on the non-uniform reduction: The reduction is non-trivial because the distribution Yi is only existential by the definition of weak PEG F (but the reduction needs to sample Yi efficiently). Using non-uniform reduction, we can hardwire the samples needed. It is more involved for uniform reduction: we need to rely on the construct of F (from OWF f) so that we can invert f(x) even we do not know the entropy i(x).

This is called uniform hard-core lemma. In the reduction, each Yi is sufficiently dense (with 1/n fraction we replace the inner product with a uniform bit) but maybe hard to sample (i(x)). Hence, if the reduction is equipped with an oracle that decides a potential sample, we can distinguish weak PEG (by calling a distinguisher of PEG in hybrids). Uniform HC lemma says that, given such reduction A without the oracle, we can construct an adversary B (without the oracle) that inverts OWF f. We skip the statement and proof of the uniform hard-core lemma as well as the reduction,see [Holenstein’06, Barak’08, HRV’13, BHK09] for details.

Discuss: If g is a PEG, is g also a OWF?

PRG from PEG

Theorem: PRG from PEG of Known Min-Entropy

Suppose g:{0,1}n{0,1}n is a PEG such that H(g(Un))=k is known, where kn. Let h1:{0,1}n{0,1}l1,h2:{0,1}n{0,1}l2 be pairwise independent hash functions sampled uniformly at random from H1,H2, where l1,l2 are chosen properly later. Let G to be the function

G(x,h1,h2):=(h1,h1(x),h2,h2(g(x))).

Then, g is a PRG.

The intuition is that:

  • Given that g(x) has pseudo min-entropy k+nα, we transform g(x) into close-to-uniform random bits using h2, where we preserved almost all entropy by Leftover Hash Lemma.
  • Observe that there are some remaining entropy in x given g(x) (because knnα in PEG). We can obtain almost all of them using h1 by Leftover Hash Lemma.

It suffices to show that

  1. D0:=G(Un,Ul1,Ul2) is statistically close to D1:=(h1,Ul1,h2,h2(g(Un))), and
  2. D1 is computationally indistinguishable from D2:=(h1,Ul1,h2,h2(Y)), where Y is indistinguishable from g(Un) and H(Y)k+nα.
  3. D2 is statistically close to D3:=(h1,Ul1,h2,Ul2).

For 1, observe that D0 is ϵ1-close to D1 by Leftover Hash Lemma when l1nkd. It is because that except for a negligible fraction ϵ(n) of x, the min-entropy of g(x) is at most k, and thus the set g1(g(x)) is at least 2nk.* Including the negligible fraction, the statistical difference is at most ϵ1:=2d/2+ϵ(n).

For 2, it follows by standard reduction (computational indistinguishability is closed under efficient operations).

For 3, observe that k+nαH(Y)n by G is PEG. By Leftover Hash Lemma, D2 is 2d/2-close to D3 when l2k+nαd.

We choose d:=nα/4 so that 2d/2 in the above is negligible. The input size of G is n+2n+2n, while the output size is

2n+l1+2n+l2=2n+(nkd)+2n+(k+nαd)=3n+2n+nα/2,

which is expanding as wanted.

* The argument is oversimplified because the set g1(g(x)) can be smaller than 2nk when g(x) happens w.p. less than 2k (yet the min-entropy k still holds). An simple fix is to observe and use the fact that except for a negligible fraction, g(x) happens w.p. 2k(1±β) for a small fraction β, which we has derived in the earlier PEG construction. That gives sufficiently large g1(g(x)) and thus large min-entropy nk(1+β), and then we choose l1:=nkkβd. Because kβ is dominated by O(nα), the output length will go through.

Finally, it remains to show that we can construct PRG from PEG without knowing the min-entropy k. We can achieve that by enumerating all possible k from 1 to n, that is

G(x1,...,xn):=G1(x1)G2(x2)...Gn(xn),

where each Gk assumes the given PEG gives min-entropy k. Because the given PEG must give min-entropy k for some k (for all input), the output of G is pseudorandom even all other kk are not. This, unfortunately, shrinks the output length by n, and that is not acceptable since we expanded only nα=o(n) bits in PEG.

The trick is that for each Gk, construct G^k such that expands to Ω(n2)+1 bits (which is exactly the same as expanding PRG from 1-bit to many-bit expansion), and then construct G from XORing G^k for all k[n]. Thus, the input is O(n2) while the output is Ω(n2)+1, expanding as wanted.

Discuss We can use less XORs to get better result. Observe that given entropy gap of PEG g is Δ=nα, we can increment the possible k by a fraction Δ/2. That is,

G(x1,...,x2n/Δ:=i[2n/Δ]G1+iΔ/2(xi).

Notice that for any k[n] such that g is PEG, there exists i such that G1+iΔ/2 is also a PRG by narrowing the gap in the construct of G by 1/2. The input length is (3n+2n)2n/Δ, and the output length is 3n+2n+Δ, which is still shrinking (but much better).

Also notice that the expansion calls the underlying PEG and thus OWF sequentially, which is also improved in later constructs [HRV’13].

This concludes the construction from OWF to PRG.