5.4: Extending the Stretch of a PRG

Recall that the stretch of a PRG is the amount by which the PRG’s output length exceeds its input length. A PRG with very long stretch seems much more useful than one with small stretch. Is there a limit to the stretch of a PRG? Using only \(?\lambda\) bits of true uniform randomness, can we generate \(100\lambda\), or even \(\lambda^3\) pseudorandom bits?

In this section we will see that once you can extend a PRG a little bit, you can also extend it a lot. This is another magical feat that is possible with pseudorandomness but not with truly uniform distributions. We will demonstrate the concept by extending a PRG with stretch \(\lambda\) into one with stretch \(2\lambda\), but the idea can be used to increase the stretch of any PRG indefinitely (see the exercises).

Construction \(\PageIndex{1}\) : PRG Feedback

Let \(G : \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}\) be a length-doubling PRG (i.e., a PRG with stretch \(\lambda\)). When \(x \in \{0,1\}^{2\lambda}\), we write \(x_{left}\) to denote the leftmost \(\lambda\) bits of \(x\) and \(x_{right}\) to denote the rightmost \(\lambda\) bits. Define the length-tripling function \(H : \{0,1\}^{\lambda} \rightarrow \{0,1\}^{3\lambda}\) as follows:

Claim \(\PageIndex{1}\) :

If \(G\) is a secure length-doubling \(PRG\), then \(H\) (defined above) is a secure length-tripling \(PRG\).

Proof:

We want to show that \(\mathscr{L}^H_{\text{prg-real}} ≋ \mathscr{L}^H_{\text{prg-rand}}\). As usual, we do so with a hybrid sequence. Since we assume that \(G\) is a secure \(PRG\), we are allowed to use the fact that \(\mathscr{L}^G_{\text{prg-real}} ≋ \mathscr{L}^G_{\text{prg-rand}}\). In this proof, we will use the fact twice: once for each occurrence of \(G\) in the code of \(H\).

The starting point is \(\mathscr{L}^H_{\text{prg-real}}\), shown here with the details of \(H\) filled in.

The first invocation of \(G\) has been factored out into a subroutine. The resulting hybrid library includes an instance of \(\mathscr{L}^G_{\text{prg-real}}\).

From the PRG security of \(G\), we can replace the instance of \(\mathscr{L}^G_{\text{prg-real}}\) with \(\mathscr{L}^G_{\text{prg-rand}}|). The resulting hybrid library is indistinguishable.

A subroutine has been inlined

Choosing \(2\lambda\) uniformly random bits and then splitting them into two halves has exactly the same effect as choosing \(\lambda\) uniformly random bits and independently choosing \(\lambda\) more.

The remaining appearance of \(G\) has been factored out into a subroutine. Now \(\mathscr{L}^G_{\text{prg-real}}\) makes its second appearance

Again, the PRG security of G lets us replace \(\mathscr{L}^G_{\text{prg-real}}\) with \(\mathscr{L}^G_{\text{prg-rand}}\). The resulting hybrid library is indistinguishable.

A subroutine has been inlined.

 

Similar to above, concatenating \(\lambda\) uniform bits with \(2\lambda\) independently uniform bits has the same effect as sampling \(3\lambda\) uniform bits. The result of this change is \(\mathscr{L}^H_{\text{prg-rand}}\).

Through this sequence of hybrid libraries, we showed that:

\(\mathscr{L}^H_{\text{prg-real}} \equiv \mathscr{L}_{\text{hyb-1}} ≋ \mathscr{L}_{\text{hyb-2}} \equiv \mathscr{L}_{\text{hyb-3}} \equiv \mathscr{L}_{\text{hyb-4}} \equiv \mathscr{L}_{\text{hyb-5}} ≋ \mathscr{L}_{\text{hyb-6}} \equiv \mathscr{L}_{\text{hyb-7}}\equiv \mathscr{L}^H_{\text{prg-rand}}\).

Hence, \(H\) is a secure PRG.