Can we build perfect secure ciphers whose key spaces are small?

We tend to believe that having a big keyspace is necessary to ensure the secrecy of our information. While this belief is correct for most of our communications, there will be cases when we can obtain perfect secure ciphers whose key spaces are small. 

We need to check Shannon’s definition of Perfect Secrecy to see how it is possible. Claude Shannon has many contributions. One of his main contributions was the transformation of cryptography from an art into a rigorous science using probability theory. 

In his work, entitled "Communication Theory of Secrecy Systems"¹,  Shannon defined the concept of Perfect Secrecy and proved that the Vernam Cipher is perfectly secure.  Shannon stated that "“Perfect Secrecy” is defined by requiring of a system that after a cryptogram is intercepted by the enemy the a posteriori probabilities of this cryptogram representing various messages be identically the same as the a priori probabilities of the same messages before the interception." 

Shannon added, "It is shown that perfect secrecy is possible but requires, if the number of messages is finite, the same number of possible keys."

This means if the message's space is small, the keys' space can be as small as the message space!  and yet it can provide perfect secrecy according to Shannon’s definition. 

At first glance, someone may think it is not secure to use a cryptosystem that can use only 3 possible keys, but it turns out it is possible. To prove this statement, I will consider the shift cipher, which is known to be insecure because of its small keyspace size. However, based on Shannon's definition, we can show that the shift cipher can be perfectly secure if we carefully select our message space. Let's illustrate this idea.

In the shift cipher, the key space has only 26 six possibilities, which is very small : $$ K= \{0, ..25\} $$

The messages are encrypted by shifting them according to some key value and then reducing them to mod 26: $$ E= (M+K)\mod26$$

Let's now take a finite space of messages which is : $$ M= \{a, b, c, d, ....z\} $$

This type of messages can be used when Bob (the recipient) asks Alice (the sender) to draw every time one card out of the possible 26 cards and to send him the result of the draw without letting Eve (the interceptor) know the result of the draw.

Because Alice will draw every card randomly, the probability distribution of every message is 1/26. This information is known to Eve and called by Shannon a priori probability. 

According to Shannon, any cipher is perfectly secure if $$ P(M=m | E=c)=P(M=m) $$ Eve cannot increase her knowledge after observing the encrypted text E=c. Any cryptosystem is perfect if it doesn't allow Eve to predict the encrypted messages with better probability (i.e., a posteriori probability) than the one known by Eve about the clear messages (i.e., a priori probability). Let's illustrate this.

Suppose that Eve has intercepted the encrypted message "c". In this case, Eve needs to list all the possibilities that can give the encrypted text "c".

M=c, K=0 | M=b, K=1 | M=a, K=2 |   M=z, K=3 |  M=y, K=4 |  M=x, K=5 | M=w, K=6 |   M=v, K=7 | 

M=u, K=8 |  M=t, K=9 |  M=s, K=10 |  M=r, K=11 |  M=q, K=12 |  M=p, K=13 |  M=o, K=14 |  M=n, K=15 |  M=m, K=16 |  M=l, K=17 | M=k, K=18 |  M=j, K=19 |  M=i, K=20 |  M=h, K=21 |  M=g, K=22 | 

M=f, K=23 |  M=e, K=24 |  M=d, K=25

Thus, the probability  P(E=c) is the sum of all these cases. 

Because selecting the keys and the messages are two independent events, we can calculate the probability of any of the previous cases as follows:

$$ P(M=x \land K=y) =  P(M=x) * P(K=y) $$

For example, $$ P(M=z \land K=3)= 1/26 * 1/26= 1/676 $$ 

The sum of all cases gives us the probability of encrypted text 'c': 

$$ P(E=c)=1/26 $$ 

Now we can prove that this cipher is perfectly secure by verifying whether: 

$$ P(M=x | E=c)=P(M=x) $$ where $$ x \in \{a, b, c..., z\} $$

We can calculate this conditional probability based on Bayes' Theorem:

$$ P(M=x | E=c)= {P( E=c | M= x) * P(M = x)  \over P(E=c)} $$ 

For example, $$ P(M=z | E=c)= {P( E=c | M= z) * P(M = z)  \over P(E=c)} $$ 

$$ P( E=c | M= z) = 1/26 $$ because there is only one possibility to obtain the encrypted text 'c' when K=3.

 

$$ P(M = z)= 1/26 $$ because Alice is drawing cards randomly. 

Thus:

$$ P(M=z | E=c)= {1/26 * 1/26 \over 1/26}= 1/26 $$ We can conclude thus that $$ P(M=z | E=c)= P(M=z) $$

Our shift cipher is thus perfectly secure! This means there is no other cipher in the world that can provide better security than this shift cipher.

It then becomes curious to know why the shift cipher is known to be very insecure. The short answer is that the security of the shift cipher ( and any cipher) depends on the space of the keys compared to the space of messages we want to encrypt. To show this, let's change our set of finite messages but keep using the same keyspace.

Let's suppose that Alice now wants to encrypt a set of messages that are composed of three letters that are:  

$$ M= \{aaa, aab, aac, aad, ......, zzz\} $$ 

The number of possible messages is 26 ^ 3.  We suppose here that the probability distribution of selecting these messages is uniform: $$ P(M = x)= 1/26^3 $$ where $$ x  \in  \{aaa, aab, aac, aad, ......,zzz\} $$ This information is known to Eve (the interceptor). 

As per Shannon’s definition, any ideal system should give adversary alternatives whose probability must be equal to 1/26^3. However, in our case, the adversary will have different options whose probability is only 1/26. To check that, let's consider that Alice has selected the key k =2 to encrypt the message "aaa"; the encrypted text will be "ccc". 

When Eve sees the message "ccc", she knows that the clear message is a three repeated letters message. There are only 26 cases when this can happen M=ddd, k=1|  M=eee, k=2...M=bbb, k=25.

P(E= ccc) is the sum of all these cases. The probability of  every case can be calculated as follows: 

$$ P(M=aaa \land K=2) =  P(M= aaa) * P(K=2) = 1/26^4$$ 

Consequently, P(E= ccc)=1/26^3. 

Our cipher is very insecure because : 

$$ P(M=aaa | E=ccc) ={P( E= ccc | M= aaa) * P(M = aaa)  \over P(E= ccc)} =(1/26*1/26^3)/1/26^3=1/26  $$

Clearly, the problem comes from the size of our key space which is only 26. According to Shannon, the size of key space must be equal or superior to the size of message space. 

As a consequence, obtaining an ideal perfect secure cipher, whose key space is small, is totally possible as long as it is equal or bigger than the message space size. 

Repeating a key in a perfectly secure cipher 

Many know that we can not use the same key to encrypt two messages in a perfectly secure cipher.  But this can be interpreted wrongly by excluding a key that has been used from the key space. Doing so leads to shortening the key space, and makes it easier for an adversary to decrypt the messages.  In fact, we can use the same key to encrypt two messages as long as our key selection is completely random. The adversary being uncertain about the key selection, the number of alternatives will remain equal to the message space.

To understand this point, let's rephrase Shannon's definition by affirming that any cipher system that enables an adversary to have several alternatives equal to the size of message space is a Perfect Secure Cipher.  

Let's take the previous example with message space equal to 26^3. If the number of alternatives after observing a cipher-text is equal to 26^3, then our cipher would be perfectly secure.

In our previous example, the cipher was insecure because the same key was used to encrypt the three letters messages. The adversary knows that he will have only 26 alternatives to decrypt any message. This comes from the fact that the probability of selecting a key for the first letter is 1/26 while the probability of selecting a key for the second and the third letters is equal to 1. 

If the adversary is uncertain whether the sender is repeating the same key or not for the second and the third letters, the probability of the key selection becomes equal to 1/26^3. The number of alternatives that the adversary will have now is equal to 26^3, even though the same key was used to encrypt the three letters. 

So it is not about repeating the keys; it is about the adversary being certain that you are repeating the keys.

References

1. Claude E.Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal, Vol. 28-4, page 656-715, Oct.1949.