PRG from any OWF
We assume that the OWF
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
… 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
is pairwise independent if the following two conditions hold when is a function chosen uniformly at random from :
- For all
, the random variable is uniform in . - For all
, the random variables and are independent. [V, Definition 3.21, p64]
Lemma: Pairwise independent hash from linear mapping.
For any finite field
, define to be the following set:
is a pairwise independent hash family. We often abuse notation, denoting to be the seed and to be the evaluation of the hash function. [V, Construction 3.23, p65]
If
Corollary:
For any
, there exists a pairwise independent hash family such that each is bits. [V, Theorem 3.26, p66]
Definition: statistical difference
For random variables
and taking values in , their statistical difference (also known as variation distance) is . We say that and are -close if . [V, Definition 6.2, p169]
Fact:
For any
, and random variable , if is -close to , then , where denotes the support of .
Definition: entropy measures
Let
be a random variable. Then
the Shannon entropy of
is: the min-entropy of
is: where all logs are base 2.
[V, Definition 6.7, p171]
Definition: -source
A random variable
is a -source if , i.e., if . [V, Definition 6.9, p173]
Definition: -extractor
A function
is a -extractor if for every -source on , is -close to . [V, Definition 6.13, p176]
Theorem: Leftover Hash Lemma
If
is a pairwise independent family of hash functions where , then is a standard -extractor. [V, Theorem 6.18, p179]
Corollary: Guessing the hash value
Let
be a pairwise independent hash family, from -bit strings to -bit strings. For any random variable such that , where
denotes the prefix bits of .
Weak Pseudo-Entropy Generator (PEG)
The first step, a gap in Shannon entropy and pseudo-entropy.
Definition: weak PEG
A function
is called a weak pseudo-entropy generator(PEG), if there exists a such that
- There exists
such that and . (This is called pseudo Shannon entropy.) .
Discuss Is a weak PEG also a weak OWF?
Theorem: Weak PEG from OWF
Let
for all be a OWF, let be a pairwise independent hash family that for each , and . Define function to be the following: where
is abused to denote the description of , denotes the -bit prefix of . Then, is a weak PEG.
Intuition for the construct:
is GL hardcore lemma, the starting point to obtain a pseudo-random bit (i.e., pseudo-entropy). However, gives no extra pseudo-entropy for many-to-one . is attempting to obtain PE by “identifying different” through . However, by randomizing , any may map to (like OTP), bad identification. is giving , and we get good identification. However, too good to be easy to invert since solving is easy. is cutting short to make inverting hard. For proper choice of , this works, but is hard to compute.- We end up with guessing random
. It works, the proof follows below.
For each
Claim: Low Shannon entropy
We have
for all (proof left as exercise). Hence, it suffices to show that . Conditioned on , we have . We want to show that when conditioned on , , which happens w.p. . It remains to show that . We will show that given , w.h.p. it holds that is uniquely determined, and thus is also determined (and gives 0 Shannon entropy). For any
and , define the pre-image set . Notice that . By is pairwise independent, for any , To see
is determined over the random , by union bound and then by
is small. (The calculation of conditional entropy is left as exercise.)
Claim: High pseudo-entropy
Proof Sketch.
Because
differ only when , assume for contradiction, there exists NUPPT , polynomial , such that for inf many , where
. We want to construct
that inverts . We have a similar claim of good ’s: let to be the set Then,
. We can next fix similarly: for each , let to be the set Then,
, where . Now, we can condition on
and . Namely, given , tries all and samples uniformly, and we have that and w.p. . It remains to find the correct so that can run repeatedly using pairwise independent ’s. Suppose that
is fixed and is sampled uniformly and independently from . Given , the min-entropy of is because each can be mapped to . By the corollary of Leftover Hash Lemma, “guessing the hash value”, the first bits of is -close to uniform. This implies that we can hit the first bits of w.p. by sampling them uniformly at random. However, to apply
, we also conditioned on (instead of uniform ). Hence, we need to take union bound:
w.p. - the guess is not the first
bits of for all w.p. . Thus, choosing
such that , we will sample a “good” input to w.p. (only conditioned on ). With the above, we can try all remaining bits and then check if the outcome satisfies . Algorithm
:
- For each
,
- For each
,
- Let
. - Run
. - Output
if . The subroutine
performs almost identical to the standard Goldreich-Levin, and the only difference is that takes additional input . Algorithm
- Let
, be fully independent and be pairwise independent -bit random strings. - For each
, sample guess bit uniformly. For each , compute the bit from in the same way as (so that for any , and for all ). - For each
,
- For each
,
- Run
. - Let
be the majority of - Output
The parameter
is choosen according to the success probability of conditioned on and and are consistent. Notice that conditioned on , the events and hits are independent, w.p. and . Also, runs over all possible and . Hence, the overall success probability is .
Discuss Is
PEG from Weak PEG
Definition: Pseudo-entropy generator (PEG)
A function
is called a pseudo-entropy generator(PEG), if there exists a such that
- There exists
such that and for some constant . (This is called pseudo min-entropy.) with probability for negligible and small fraction . More precisely, there is a such that and that for all , .
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
is a weak PEG. Let to be the function where
for all , and is a polynomial (to be chosen later). Then, is a PEG.
Discuss The construction of
Let
- The min-entropy
can be (which is not good for our purpose); that means - There exists bad
such that ; however, - All such
can not take much probability mass over all (otherwise, the Shannon entropy would be ).
Therefore, since we repeat
- The Shannon entropy of
is . - Most of
instances in are good, - Each good gives min-entropy close to
, and thus - it gives total min-entropy close to
, 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
be the support of . Define to be the set where the probability is over
that are sampled uniformly, and . Then This implies that
for all but fraction of ’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 ’s. The idea is that repeating
for times independently “smooths” the overall distribution. Because is an average notion, a majority of satisfy that , 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
be independent random variables taking real value in , let , and let . For any , The calculation is as follows. For any
, define . where
by definition, and by definition of Shannon entropy and weak PEG.
Claim: High pseudo-min-entropy
Let
be the distribution such that is indistinguishable from but . There exists a distribution such that and that is indistinguishable from , where is a constant.
Proof sketch.
By a non-uniform reduction,
is indistinguishable from such that are sampled from independently (* see caviate below). We have Shannon entropy , but we want 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, where
for all . We simply get rid of those “bad ” from and obtain the distribution by moving the probability mass to all strings in uniformly, which yields with min-entropy at most which is at least
because as by Taylor series. Choosing and , we have the gap at least (and thus , we can choose even smaller and larger ). Notice that the entropy gap is roughly
, which incurs a huge . * Caviate on the non-uniform reduction: The reduction is non-trivial because the distribution
is only existential by the definition of weak PEG (but the reduction needs to sample 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 (from OWF ) so that we can invert even we do not know the entropy . This is called uniform hard-core lemma. In the reduction, each
is sufficiently dense (with fraction we replace the inner product with a uniform bit) but maybe hard to sample ( ). 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 without the oracle, we can construct an adversary (without the oracle) that inverts OWF . 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
PRG from PEG
Theorem: PRG from PEG of Known Min-Entropy
Suppose
is a PEG such that is known, where . Let be pairwise independent hash functions sampled uniformly at random from , where are chosen properly later. Let to be the function Then,
is a PRG.
The intuition is that:
- Given that
has pseudo min-entropy , we transform into close-to-uniform random bits using , where we preserved almost all entropy by Leftover Hash Lemma. - Observe that there are some remaining entropy in
given (because in PEG). We can obtain almost all of them using by Leftover Hash Lemma.
It suffices to show that
is statistically close to , and is computationally indistinguishable from , where is indistinguishable from and . is statistically close to . For 1, observe that
is -close to by Leftover Hash Lemma when . It is because that except for a negligible fraction of , the min-entropy of is at most , and thus the set is at least .* Including the negligible fraction, the statistical difference is at most . For 2, it follows by standard reduction (computational indistinguishability is closed under efficient operations).
For 3, observe that
by is PEG. By Leftover Hash Lemma, is -close to when . We choose
so that in the above is negligible. The input size of is , while the output size is which is expanding as wanted.
* The argument is oversimplified because the set
can be smaller than when happens w.p. less than (yet the min-entropy still holds). An simple fix is to observe and use the fact that except for a negligible fraction, happens w.p. for a small fraction , which we has derived in the earlier PEG construction. That gives sufficiently large and thus large min-entropy , and then we choose . Because is dominated by , the output length will go through.
Finally, it remains to show that we can construct PRG from PEG without knowing the min-entropy
where each
The trick is that for each
Discuss We can use less XORs to get better result. Observe that given entropy gap of PEG
is , we can increment the possible by a fraction . That is, Notice that for any
such that is PEG, there exists such that is also a PRG by narrowing the gap in the construct of by 1/2. The input length is , and the output length is , 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.