How is the One Time Pad (OTP) perfectly secure?

Question

The Wikipedia entry on One Time Pads (OTPs) states that if this cipher is used properly; ie, the keys are truly random and each part of the key is independent of every other part, it's uncrackable, and yields perfect secrecy, i.e., $H(M|C) = H(M)$.

It gives an example saying that a cryptanalysis on a plaintext "HELLO" will yield all plaintexts like "HELLO", "LATER", with equal probabilities.

Now, consider some OTP encrypted data that I know are English sentences. With infinite computational power, I generate all plaintexts. Now, becasuse each word of the sentence is related to nearby words, I can at the very least narrow down the list of possibilities (I don't know the combinatorics of cramming English sentences into M letters), which does not equal perfect secrecy (entropy $H(M)$ appears to have decreased!).

In short, OTP guarantees $H(M|C) = H(M)$, but my question is that $H(M)$ will be reduced by knowledge of the plaintext, so how is prefect secrecy being ensured?

Answer 1

You've actually been trapped by the mindset that OTP will hide all information about the underlying plaintext.

This is not true as you have observed.

The definition of perfect secrecy, given in Introduction to Modern Cryptography by Katz-Lindell, reads like this:

Definition 2.3 An encryption scheme $(\text{Gen, Enc, 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\mid C=c]=\Pr[M=m]$$

In other words, if you have the ciphertext at hand, you won't learn anything new that you didn't already know about the plaintext.

The OTP satisfies this (proved in "Introduction to Modern Cryptography") and thereby is perfectly secret as an encryption scheme. In short it first shows that $\Pr[C=c\mid M=m']=2^{-l}$, then uses this to show that $\Pr[C=c]=2^{-l}$ and concludes via $\Pr[M=m\mid C=c]=Pr[M=m]$ (using Bayes' theorem).

Answer 2

You stated:

"I can at the very least narrow down the list of possibilities."

Here's an example of why OTP is perfect secrecy, and why your statement, although true, doesn't matter.

I have a sentence which I wrote, and after encrypting it with an OTP, it looks like this:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Good luck decrypting that! Maybe you can narrow that down to a few million (or billion?) English sentences, but that doesn't help you. And how would you know that it's a sentence to begin with? Furthermore, as the size of the data increases, the number of possibilities approaches infinity. Even a single character message is impossible to decrypt:

a

You can narrow a single character down to 128 (or 256 or 65K depending on the encoding) possibilities, but again, that doesn't really help you much.

Answer 3

What you propose is equivalent to trying to do cryptanalysis without any cipher text or other material.

Equivalently, you could just take the small plaintext seed that you know, and nothing else, and run it through a probabilistic language model to predict the most likely message. (e.g., a Markov chain text generator). Obviously, it doesn't get you very far...

Consider for example, that one knowns the plaintext "attack at d___". I for one would be reluctant to rely entirely on a language model to decide if I should ready my defences for "dawn" or "dusk".

The key point here is that, all things being equal, access to the OTP-encrypted cipher text gives you no new information (beyond perhaps an upper bound on message length).