1
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ Clearly entropy of m is the wrong measure here. Otherwise the length of the ciphertexts must reveal the entropy of the message. The thing is that perfect secrecy is defined over a set of messages. Generally in most definitions this set is $\{0,1\}^*$. You just chose to use a different set of messages. That does not change the general statement. For a message of length n you need a key consisting of n random elements of your alphabet. $\endgroup$
    – Maeher
    Feb 19, 2018 at 1:20
  • 3
    $\begingroup$ Another way of saying what @Maeher has already said: perfect secrecy should hold for all message distributions, including the uniform one. In this case the entropy of the message is equal to the its length. (We also assume the key is chosen uniformly at random, such that the key entropy and length are equal.) $\endgroup$
    – Aleph
    Feb 19, 2018 at 11:46
  • 1
    $\begingroup$ Which definition of entropy are you using? Shannon? Min entropy? Max entropy? $\endgroup$ Feb 20, 2018 at 11:27
  • 2
    $\begingroup$ @PaulUszak Your confusion may come from your standard OTP key of random 0-255 value bytes which is bluntly wrong. An OTP key has to be completely random within the "alphabet" you're using. Random bytes may be handy in the world of computers as it exactly fits the hardware expectations… but OTP can also be applied to other symbol ranges with different bit sizes. One could even apply OTP on a 0-1 symbol range (think bit-wise instead of byte-wise) as long as the series of 0s and 1s is absolutely random. Take a simple Y/N msg, and your entropy theories can be voided with a simple coin flip. $\endgroup$
    – e-sushi
    Feb 21, 2018 at 12:48

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ No, you're wrong. You've made a mistake about what the message is. The message is whatever data you actually send. It doesn't matter if it's compressed or not. It doesn't matter how much entropy it has. All that matters for a one-time pad is how many bits get sent. $\endgroup$ Feb 21, 2018 at 14:34
4
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ But your example is completely wrong. Your 5 byte message can be compressed down to 1 byte, XORed with the 1 byte key and still maintain perfect secrecy. Remember, long run English compresses 5 fold (8/1.6). Not really sure where the repeated key bit comes from though... $\endgroup$
    – Paul Uszak
    Feb 19, 2018 at 22:19
  • $\begingroup$ @PaulUszak It is not at all clear to me how/why that is so. How exactly would you compress the 5 byte message to 1 byte? If you are assuming the existence of such a compression algorithm, it would be helpful to state so explicitly. Additionally, it would simply change the situation to "What if I apply an 8-bit random key to an 8-bit message", to which the answer is obvious. The repeated key bit is a pre-emptive answer to a possible question that I anticipated may be asked in response to the rest of the answer. $\endgroup$
    – Ella Rose
    Feb 20, 2018 at 1:40
  • $\begingroup$ Not 5 bytes $ \to $ 1 byte, but 5MB $ \to $ 1MB yes. Comprehensibility is a function of entropy. Anything with an entropy of 1.6 can be compressed five fold. That's the definition of compression. Shakespeare's complete works (~5MB) compress ~5 fold, therefore a OTP key to hide Shakespeare only needs to be ~1MB. And I did talk about long messages :-) $\endgroup$
    – Paul Uszak
    Feb 20, 2018 at 11:20
  • 2
    $\begingroup$ @PaulUszak I don't see how $5\ unit_a \rightarrow 1\ unit_a$ is a different case from $5 unit_b \rightarrow 1\ unit_b$, especially when $unit_a$ is the basis of $unit_b$. My example is simply more convenient when displayed with 5 byte messages instead of 5MB messages. I understand that your question talks about sufficiently long messages, but it does not mention compression anywhere, nor talk about how that changes anything. From these comments it sounds like your question is "what if we compress english text before applying a OTP", which is not what is stated in your original post. $\endgroup$
    – Ella Rose
    Feb 20, 2018 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.