# If a cipher has key length shorter than plaintext, then it is not perfectly secure

I am trying to verify the statement above. So far I only know that a One-Time-Pad is the only “perfectly secure” cipher. It has a key length which is exactly the same as the plaintext. I think the statement is true but I don't know how to prove it…

Can anyone give me some hints or point me to an according reference or two?

• Consider: what does it mean for a cipher to be perfectly secure in the first place? – Stephen Touset Oct 5 '14 at 20:34

Here's a more "down to earth" example. The following cryptosystem with plaintext space $\mathcal{M} = \{a,b,c,d\}$, keyspace $\mathcal{K} = \{1,2,3,4\}$ and ciphertext space $\mathcal{C} = \{A,B,C,D\}$ has perfect secrecy:

$$\begin{array}{c|c c c c} & 1 & 2 & 3 & 4 \\ \hline a & A & B & C & D \\ b & B & C & D & A \\ c & C & D & A & B \\ d & D & A & B & C \end{array}$$

if the key is chosen uniformly at random independently of the plaintext (the table should be read as saying that, for example, encryption of the plaintext $a$ with the key $3$ yields the ciphertext $C$). The perfect secrecy means that an attacker who obtains a ciphertext has no "hint" about what the plaintext may be: for example if an attacker obtains the ciphertext $C$, it could be the result of encrypting the plaintext $a$ with the key $3$, or the plaintext $b$ with the key $2$, or the plaintext $c$ with the key $1$, or the plaintext $d$ with the key $4$, and all those cases will occur with probability $1/4$. By comparison, the following cryptosystem:

$$\begin{array}{c|c c c c} & 1 & 2 & 3 & 4 \\ \hline a & A & A & C & D \\ b & B & C & D & A \\ c & C & D & A & B \\ d & D & B & B & C \end{array}$$

does not have perfect secrecy because if an attacker obtains the ciphertext $A$, he knows that the plaintext is not $d$, and it is also more likely that the plaintext is $a$ (which is the case with probability $1/2$) than $b$ or $c$ (probability $1/4$ each).

On the other hand, with the following cryptosystem with keyspace $\mathcal{K}' = \{1,2,3\}$:

$$\begin{array}{c|c c c c} & 1 & 2 & 3 \\ \hline a & A & B & C \\ b & B & C & D \\ c & C & D & A \\ d & D & A & B \end{array}$$

an attacker obtaining the ciphertext $A$ knows that the plaintext is not $b$, so this system does not have perfect secrecy either, and it is easily seen that any cryptosystem with fewer keys than plaintexts will have the same problem.

• You should not call the 2nd example a cryptosystem, because under key $2$ your function is not injective: a and d both are encrypted as A, so decryption is impossible. – tylo Mar 9 '15 at 10:34

Imagine that you have a ciphertext:

• Perfect secrecy means, that without knowing the key, any plaintext has to be a possible preimage. Because otherwise the ciphertext would give you information about the plaintext.
• Encryption is an injective function, because otherwise it could not be reversed. That means, for a given key and ciphertext you have at most one possible preimage.
• Then it is just an argument about the sizes of the sets of plaintexts and keys: If the keyspace is less than the keyspace, then there is no key for some pair $(p,c)$, and it can't be perfectly secure any more.

If the key would be smaller than the plaintext then you could brute force the cipher by using less than $N$ steps, where $N$ represents the amount of possible messages.

Of course the brute force approach is an upper bound to what can be tried. If there are attacks on the cipher (that are less complex than brute force) then the plaintext may be recovered more easily, something that is impossible using a pure OTP.

Please take a look taken from the Wikipedia page for OTP for a more formal description of perfect secrecy:

This is because, given a truly random key which is used only once, a ciphertext can be translated into any plaintext of the same length, and all are equally likely. Thus, the a priori probability of a plaintext message $M$ is the same as the a posteriori probability of a plaintext message M given the corresponding ciphertext. Mathematically, this is expressed as $H(M)=H(M|C)$, where $H(M)$ is the entropy of the plaintext and $H(M|C)$ is the conditional entropy of the plaintext given the ciphertext C. Perfect secrecy is a strong notion of cryptanalytic difficulty.

and

Given perfect secrecy, in contrast to conventional symmetric encryption, OTP is immune even to brute-force attacks. Trying all keys simply yields all plaintexts, all equally likely to be the actual plaintext. Even with known plaintext, like part of the message being known, brute-force attacks cannot be used, since an attacker is unable to gain any information about the parts of the key needed to decrypt the rest of the message.

• Perfect secrecy is not about any time bound attacker. The point is not that brute force takes some smaller number of steps, but that trying all keys gives you less than all messages with a smaller key size. – Paŭlo Ebermann Mar 8 '15 at 17:14