When I learn the Stanford online course, Cryptography I, I am confused on the Advantage definition:
The purpose is let Adv[A,G] be "negligible" . I can consider it is nearby zero. There are 4 cases of the Adv in the below table:
Pr[A(G(k))=1] Pr[A(r)=1] Adv[A,G]
------ ------------- ---------- --------
Case 1 0 0 0
Case 2 1 0 1
Case 3 0 1 1
Case 4 1 1 0
Be careful that:
The "0" in the table means nearby zero.
The "1" in the table means nearby one.
We don't care about case 1 and case 2 where,
Pr[A(r)=1] = 0.
The formula is equal to
Pr[A(r)=0] = 1,
that means the statistical test A determines the r is not random. Actually r is a uniform random variable on {0,1}^n. Therefore we cannot find any statistical test to determine r is not random.
For Case 3, the PRG, G, is bad because it is not random determined by the statistical test, A.
Therefore only Case 4 are what we concern. Why is the Adv "negligible" in Case 4? I consider the reason is,
Pr[A(G(k))=1]
is not exactly equals to one.
-Count
SItus Terpercaya
ReplyDelete