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