If PRG is predictable, PRG is insecure.

The Stanford on-line course, Cryptography I, proof that "If PRG is secure, PRG is unpredictable". The statement is equal to "If PRG is predictable, PRG is insecure".

Below is the definition of "predictable".



The steps of the proof are below.



(I'm sorry I directly copy the pictures from the course because it is hard to write the math statements by typing. If the original author concern it, please let me know and I'll remove them.)

The question is, why is the statement true?

Pr[B(r)=1] = 1/2 

The statement in the probability

B(r)=1, 

is equal to

A(r(i...i)) = r(i+1)

Let's calculate the probability.

A(r(i...i)) r(i+1)
----------- ------
          0      0
          0      1
          1      0
          1      1


We specify that

Pr[A=0] = p0
Pr[A=1] = p1
where p0 + p1 = 1

(We cannot say p0 = p1 = 1/2.)

Obviously,

Pr[r(i+1) = 0] = 1/2
Pr[r(i+1) = 1] = 1/2

because r is a uniform random variable.

Pr [A = r(i+1)] = Pr[A=0] * Pr[r(i+1)=0] + Pr[A=1] * Pr[r(i+1)=1]
= p0 * 1/2 + p1 * 1/2 = (p0 + p1) / 2 = 1/2.

because the i+1 bit is independent of the first i bits.


-Count