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,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:

-Count

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:

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

-Count

## No comments:

## Post a Comment