STUDY NOTES CRYPTOGRAPHY I – Statistical Tests

Statistical test on {0,1}^n:

an algorithm A such that A(x) outputs “0”(not random) or “1”(random)

A(x) = 1 if and only if the number of generated 1s are not hugely different from the number of 0s

A(x) = 1 if and only if the number of two consecutive 0s are not dramatically different from a quarter of the total number of bits.

A(x) = 1 if and only if max-run-of-o(x) <= 10 * log2(n)

Advantage[A,G] = | Pr[A(G(k))=1] – Pr[A(r)=1] |

Advantage close to 1 -> A can distinguish G from random

Advantage close to 0 -> A cannot distinguish, or the PRG is pretty much like random

secure PRG <=> Advantage[A,G] is negligible for all efficient statistical tests.

Thm(Yao’82), an unpredictable PRG is secure

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s