Tuesday, September 20, 2016

What does mean "Advantage"

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

1 comment: