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