# An unpredictable PRG is secure (Theorem Yao'82)

in the Mr Boneh's online course is stated the following theorem:

Let $G:K \to \{0,1\}^n$ be a PRG.

“Thm”: if $\forall i \in \{0, … ,n-1\}$ the PRG $G$ is unpredictable at pos. $i$, then $G$ is a secure PRG.

Moreover, according to his words, proving this is just a "puzzle" to prove, but actually I can't see it so easily, the only idea I have at the moment is arguing that if you can't predict the next bit of some pseudo-random string, then you can't distinguish between that pseudo-random string and a that pseudo concatenated with a truly random one in that position, It's a nice beginning but I don't know how to exploit it. Can someone give me a hand in the argument for the proof? Thank you very much.

PS: Here you can find the definition of unpredictable, secure PRG we've used and the theorem itself (Althought in my opinion, those definitions as stated there are not satisfactory from a mathematical point of view).

-
I think a proof sketch using contraposition might go: Assume $G$ is not a secure PRG. There is thus an algorithm that breaks $G$. Define $G_i$ which substitutes true random to bits at position $j\ge i$. The same algorithm breaks $G_n$ (since that's $G$) but not $G_0$ (since that's random). So there must be a $i$ such that it breaks $G_{i+1}$ but not $G_i$. Now you can build a predictor for position $i$. –  fgrieu Jul 8 '14 at 6:53

This lecture (PDF) has the solution in section 3.

Here's my informal explanation of the proof:

We have an unpredictable PRG $G$. We want to show that $G$ is secure, or in other words indistinguishable from $R$ (I'll use = to mean indistinguishable whenever referring to two distributions for the remainder of the proof).

Using the notation that $G_k R_{n-k}$ means get the first $k$ bits using $G$ and generate the last $n-k$ bits totally randomly, it suffices to show that $G_{i-1} R_{n-i+1} = G_{i} R_{n-i} \ \forall i$, since then $G_n = G_{n-1} R_1 = G_{n-2} R_2 ... = R_n$ by a trivial induction, and $G_n$ is $G$, $R_n$ is $R$ by definition.

So we want to show that for all $0 \le i \le n-1$, $G_{i-1} R_{n-i+1} = G_{i} R_{n-i}$.

Assume for sake of contradiction that this doesn't hold for some $i$. That means there is some statistical test $A$ which can distinguish $G_{i-1} R_{n-i+1}$ from $G_{i} R_{n-i}$, or a statistical test where the advantage is non negligible. This means that either $A$ is more likely to equal $1$ when using $G_{i} R_{n-i}$, or more likely to equal $0$ when using $G_{i} R_{n-i}$, without loss of generality let's say $1$. So pick a random bit $b$ and run $A(G_{i-1} b R_{n-i})$.

If it returns $1$, then we'll guess that $b = g_i$ (since $A$ is more likely to equal $1$ when the first $i$ bits come from $G$); if it returns $0$, we'll guess that $b \neq g_i$. This is just a guess, but since there's a non-negligible advantage, the odds that we guessed correctly are greater than $\frac 1 2$ by the same non-negligible factor. This means we can predict the $i$th bit from the first $i-1$ bits, which contradicts our assumption that $G$ is not predictable.

-
A completely and absolutely excelent answer. Thanks a lot! –  Daniel Escudero Jul 10 '14 at 5:18