Strictly, is length(key) >= length(message) wrong for one time pads?

Question

It's a common adage that for a perfectly secret one time pad, length(key) >= length(message) must hold. But that's wrong isn't it? At least very sloppy maths. Isn't the strict mathematical requirement that:-

entropy(key) >= entropy(message)?

An example. Consider a OTP used for a message in the English language. From various studies we guesstimate that the information entropy rate of English is ~1.6 bits/character. Lets not quibble about the exact value as anything <8 will suffice for this example. Now take a standard OTP key of random 0-255 value bytes. That's an entropy of 8 bits/byte. Therefore for long English OTP messages, the key can be one 1/5 of the message length and still guarantee perfect secrecy. Essentially the message could be compressed five fold and then XORed with the much shorter binary key.

And the equation is reversible. If you encrypt binary data (say reasonably in-compressible compiled code) with a basic English alphabet, you'd need five times the length of key material compared to the message.

Clearly as the message alphabet increases, then the mathematical requirement tends towards the original adage. But isn't my general case more accurate?

Am I wrong/confused/hungry?

Answer 1

length(key) >= length(message) DOES still hold in your compressed case. The "message" that gets encrypted with the key isn't the meaning of that message, it's the literal data that gets XORed with the key. If your meaning can be compressed losslessly into a short message then the key only needs to be as long as the message, and not the meaning.

Answer 2

Your confusion stems from a misinterpretation of a formal statement about the limitations of perfect secrecy. Let us first recall the definition

Perfect Secrecy. An encryption scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ with message space $\mathcal{M}$ is perfectly secret if for every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which $\Pr[C = c] > 0$: $$Pr[M = m | C = c] = Pr[M = m].$$

Note that there is no mention of bits or bitstrings here and "length of the message" is not really well defined for a general message space. The statement that is often informally paraphrased as

The key must be at least as long as the message.

therefore doesn't really make any sense here. This is where you seem to be confused. The formal statement that can be proven about perfectly secret encryption schemes is the following:

Limitation of Perfect Secrecy. If $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ is a perfectly secret encryption scheme with message space $\mathcal{M}$ and key space $\mathcal{K}$, then $|\mathcal{K}| \ge |\mathcal{M}|$.

Note that this is only a statement about the size of the key space! It makes no mention of any length. Now, the most well known perfectly secret encryption scheme is the one-time pad, which is most commonly defined over bitstrings¹ with a message space $\mathcal{M}=\{0,1\}^n$ for some message length $n$ as well as a keyspace $\mathcal{M}=\{0,1\}^\ell$ for some key length $\ell$. In this specific case case $|\mathcal{K}| \ge |\mathcal{M}|$ indeed implies that $\ell \ge n$.

In your specific case however you used a different message space, in particular you defined $\mathcal{M}$ to be the set of "messages in the English language" which is something we would need to define more formally. We can define this for example as "any concatenation of words in the English language with total length at most $\ell$ characters".

In this case, clearly $|\mathcal{M}| < 2^{8\ell}$ and therefore obviously you do not need $|\mathcal{K}|\geq 2^{8\ell}$ but the definition never claimed otherwise. What you are defining here is simply not the one-time-pad, but a different encryption scheme with a different message space. And the same condition on the key space still holds. It is just that this does not necessarily correspond to an immediate lower bound on the length of the keys when encoded as bitstrings.

---

¹Technically the one-time pad can be defined over strings over any finite alphabet $\Sigma$ as long as we can define an order over $\Sigma$.

Answer 3

Therefore for long English OTP messages, the key can be one 1/5 of the message length and still guarantee perfect secrecy.

If we look at the bits of the key and the bits of the message, it's pretty easy to see it doesn't work out this way:

key = 11101100

message = 01101000 01100001 01110000 01110000 01111001

11101100

01101000 01100001 01110000 01110000 01111001 +
----------------------------------------------
10000100 01100001 01110000 01110000 01111001

Well that's not good - Notice how almost all of the message bits remain unmodified? Clearly the length of the key being big enough to cover the message bits is quite important.

What if we repeat the key to cover the rest of the message bits?

Let's look:

key = 11101100

message = 01101000 01100001 01110000 01110000 01111001

11101100 11101100 11101100 11101100 11101100

01101000 01100001 01110000 01110000 01111001 +
----------------------------------------------
10000100 10001101 10011100 10011100 10010101

We have effectively re-used an 8-bit key on 5 8-bit plaintexts.

Considering that our messages were not drawn uniformly at random, they will not possess 8-bits of entropy per 8-bits of message, and therefore some message bits will be guessable.

The ability to guess these bits will allow the recovery of key bits at the corresponding locations. In turn, this may reveal enough plaintext information to reveal the entire 8-bit message, which can then be used to recover the entire 8-bit key. Then you can use the key to decrypt the rest of the message.

Is perfect secrecy still achieved?

Clearly not - which implies that we are not working with a One Time Pad anymore.