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

## No comments:

## Post a Comment