Skip to main content
Engineering LibreTexts

5.4: Extending the Stretch of a PRG

  • Page ID
    7344
  • 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:

    Screen Shot 2019-03-03 at 12.34.49 PM.png

    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\).

    Screen Shot 2019-03-03 at 12.40.12 PM.png

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

    Screen Shot 2019-03-03 at 12.41.11 PM.png

    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}}\).

    Screen Shot 2019-03-03 at 12.42.12 PM.png

    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.

    Screen Shot 2019-03-03 at 12.43.41 PM.png

    A subroutine has been inlined

    Screen Shot 2019-03-03 at 12.44.22 PM.png

    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.

    Screen Shot 2019-03-03 at 12.45.49 PM.png

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

    Screen Shot 2019-03-03 at 12.48.46 PM.png

    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.

    Screen Shot 2019-03-03 at 12.53.44 PM.png

    A subroutine has been inlined.

    Screen Shot 2019-03-03 at 12.54.16 PM.png

    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.