Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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 at 6:53

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
A completely and absolutely excelent answer. Thanks a lot! –  Devilathor Jul 10 at 5:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.