If PRG is secure, PRG is unpredictable

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

Use Advantage to Define Secure PRG

Below is the Advantage definition:




We use Advantage to define Secure PRG as below:



How do we understand the definition of secure PRG with Advantage? We can draw the below picture to describe the definition.




-Count

Understand that, One Time Pad (OTP) has perfect secrecy

A cipher (E, D) over (K, M, C) that is OTP if

K = M = C = {0, 1}^n
c = E(k, m) = k xor m
m = D(k, c) = k xor c
where c in C, k in K, m in M

OTP has perfect secrecy because |k| = |m|.

How do we understand the statement?

We can give a simple example.

K = M = C = {0, 1}^2

Below is the table of the OTP cipher.



We focus on c = 11 to guess the probability of m where k is a uniform random variable.

Pr[E(k, 00) = 11] = 1/4 
Pr[E(k, 01) = 11] = 1/4 
Pr[E(k, 10) = 11] = 1/4 
Pr[E(k, 11) = 11] = 1/4 

It describes that the OTP is perfect secrecy because

Pr[E(k, m) = c] = 1/4, for all c in C,
where k is a uniform random variable.


-Count

Perfect Secrecy ==> Key Length >= Message Length

Here is a theorem:

If a cipher (E, D) over (K, M, C) is a perfect secrecy,
then k length >= m length, where k is K, and m is M.

How do we proof it?

We transfer the theorem as below.

If k length < m length, the cipher is not a perfect secrecy.

Therefore we just give an example to explain the theorem.

Lets

K = {0, 1}^2 = {00, 01, 10, 11}
M = {0, 1}^3 = {000, 001, ..., 111}
C = {0, 1}^3 = {000, 001, ..., 111}

Obviously k length = 2 and m length = 3

Give a table.

  M   K    C
---  --  ---
000  00  000
001  01  001
010  10  010
011  11  011
100      100
101      101
110      110
111      111

I consider it may be easy to explain the theorem if specifying elements in the table as numeric symbols.

M K C
- - -
0 0 0
1 1 1
2 2 2
3 3 3
4   4
5   5
6   6
7   7

We understand the meaning of "Perfect Secrecy". We focus c=0 and try to guess the message.

We know that

E(k, m) = c
D(k, c) = m

We can design  a cipher (E, D) for c=0 and for all k is k as below.

D = {(k,c,m)} 

where

k c m 
- - -
0 0 0
1 0 1
2 0 2
3 0 3

There is a problem that the number of keys is not enough to cover another m values:4, 5, 6, 7.

Because k is a uniform random number, we expand the probability as below.

Pr[E(k,0)=0] = 1/4
Pr[E(k,1)=0] = 1/4

Pr[E(k,2)=0] = 1/4

Pr[E(k,3)=0] = 1/4
Pr[E(k,4)=0] = 0

Pr[E(k,5)=0] = 0

Pr[E(k,6)=0] = 0

Pr[E(k,7)=0] = 0

It describes that the cipher is not perfect secrecy because

Pr[E(k,m)=0] = 1/4 or 0, for all k is in K.

Let me explain it in English. If we know the ciphertext c is 0 and the cipher algorithm, (E, D), we can guess the message, m:

1. The event, m=4, 5, 6, or 7, doesn't happen.
2. The probability of the event, m=0, 1, 2, 3, is 1/4.

-Count

How does a software engineer understand "Perfect Secrecy"?

I consider, a definition in mathematic formula format is like source code written with a computer language. Mathematic formula is written for mathematician. Source code is written for a computer.

The way to understand a mathematic definition is the same as the way to understand a source code. How do we understand source code? I believe any experienced software engineers know the trick. I also believe we can understand some mathematic definition in the same way for understanding source code.

Don't worry, we have enough ability to understand some mathematic definition. For example, below is the definition of "perfect secrecy":



The definition is a formula that is compressed from many sentences. How do we understand it? A better way is try to decompress the formula to get original sentences and understand them.

We know that,

E(k, m) = c
D(k, c) = m

I explain the perfect secrecy that:

1. I know the ciphertext, c.
2. I know the encryption and decryption algorithms, E and D.
3. It is hard to guess the key, k, because it is a uniform random variable. The probability of successfully guessing is 1/|K|.
4. It is hard to get a correct m by decrypting c with a guessed key because the probability of getting the correct m is the same constant for all k in K.

Our purpose is to translate the four sentences into a formal definition with a formula.

First, try to translate the above sentences in a informal formula.

E(k?, m?) = c

It means:

• I know the ciphertext, c, and encryption algorithm, E.
• I don't know k and m.

Translate it into another informal formula.

E(k, m?) = c
where k is a uniform random variable on K

Because m is deterministic by D(k, c) = m, we translate it again.

E(k, mi) = c
where k is a uniform random variable on K

and i = 0, 1, ..., |M|

Finally we add the 4th sentence to complete the formal definition of "perfect secrecy".

Pr[E(k, mi) = c] = constant

where k is a uniform random variable on K

and i = 0, 1, ..., |M|

-Count

Negligible and non-negligible - A better explanation

The page, Negligible and non-negligible, explains what means

lambda >= lambda d 

in the definition of negligible and non-negligible,



by using the below formula,

g(x) = 2^x - x^d >= 0

to draw the below picture,



Actually, we can using another formula to draw a more beautiful picture. We derive the formula as below:

We except that:

f(x) = 1/(2^x) <= 1/(x^d)

We define that:

g(x) = (x^d) / (2^x) <= 1

And draw the below picture for d = 2, 3, 4.




Please look at the red lines:

For d = 2, g(x) <= 1, if x >= 4
For d = 3, g(x) <= 1, if x >= 9.94...
For d = 4, g(x) <= 1, if x >= 16

The values, 4, 9.94..., and 16 are of "lambda d".

-Count

Uniform Random Variable v.s. Identify Function.

We know that a random variable r.v. is actually a function. Can we confirm that a uniform random variable must be an identity function? I don't think so. I also have not found that the identify function is a part of the definition of the uniform r.v. yet. Let me explain why.

Below is the r.v. definition:

X: U ---> V

Because r.v.  is also a function, I like write it as below only for easily thinking for me.

f: X ---> Y

The uniform r.v. is defined as below.

f: X ---> Y, Y = X
Pr [f(x) = y] = 1 / |X|

Below is the definition of identity function.

f: X ---> X
f(x) = x for all x is X

We define two random variables, f1 and f2, with same X and Y as below.

X = {0, 1, 2, 3}
Y = {0, 1, 2, 3}

f1: X ---> Y
f2: X ---> Y

Obviously, f1 and f2 are uniform r.v. because

Pr [f1(x) = y] = 1 / |X|
Pr [f2(x) = y] = 1 / |X|

but f2(x) is not an identity function because 

f2(x) <> x for all x is X.

However, we prefer to select the identity function, f1(x), as an uniform random variable.

So far, I answer the question myself because I have not found the answer on Internet yet. 

-Count