# Proving that a PRG is predictable

I am attending the video lectures from Prof Dan Boneh. He gives the following example.

Let $$G:\mathcal K\longrightarrow \Bbb Z_2^n$$ be a PRG with the property that from the last $$\frac{n}{2}$$ digits of $$G(k)$$ we can easily compute the first $$\frac{n}{2}$$ digits of $$G(k)$$. We want to show that $$G$$ is predictable for some $$i\in\{0,\dots,n-1\}$$.

Well, it is clear that we should use the contrapositive of Yao's Theorem. That is, if we prove that $$G$$ is not secure, then $$G$$ is predictable.

To do so, we have to define a statistical test $$B:\Bbb Z_2^n\longrightarrow \Bbb Z_2$$, and show that the advantage $$\mathrm{Adv_{PRG}}(B,G):=|\mathrm{Pr}_{k\overset{R}{\leftarrow} \mathcal K}(B(G(k))=1)-\mathrm{Pr}_{k\overset{R}{\leftarrow} \mathbb{Z_2^n} }(B(r)=1)|\in [0,1]$$ is non-negligible.

So, my question is what the statistical test $$B$$ could be?

• HINT: If someone came to you with $n$ bits from $G$, but was worried that they might have become garbled, how would you check for garbling? Mar 14 at 7:28