Below is the definition of secure PRG.

Below is the definition of predictable PRG.

How do we proof the below theorem?

PRG is secure => PRG is unpredictable

The previous page proofed it by:

PRG is predictable => PRG is not secure

This pare proofs it in a direct way. Before proofing it, I draw the below picture, where G is PRG, to understand the definition of secure PRG and unpredictable PRG.

We keep the picture in our mind and use simple formulas to proof it.

The fact is that G is secure:

Adv = |Pr [A (G) = 1] - Pr [A (r) = 1]| <= e (e is epsilon)

Because the statement, that is proofed by the page, is also true.

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

Therefore

Pr [A (G) = 1] <= 1/2 + e

We can transfer the statement from A to B for the definition of A that is a statistical test.

Pr [B (G|1...i+1) = G|i+1] <= 1/2 + e

Therefore G is unpredictable.

-Count

## No comments:

## Post a Comment