Skip to main content

# 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.