Perfect secrecy according to Shannon

The one-time pad is not merely hard to break: it is impossible to break. This claim is not a marketing slogan, it is a theorem, proved by Claude Shannon in 1949.

Claude Shannon and perfect secrecy

In his founding paper Communication Theory of Secrecy Systems, Shannon defines mathematically what it means for "an encryption scheme to be perfectly secure". His definition, called perfect secrecy, is demanding:

Observing the ciphertext must give no information about the plaintext.

In other words, the probability that a given plaintext was sent is exactly the same before and after intercepting the ciphertext. The eavesdropper learns nothing.

Why the one-time pad achieves this secrecy

The intuition is as follows. An attacker intercepts a ciphertext C. They would like to recover M. But for every conceivable plaintext M' of the same length, there exists exactly one key K' that produces this ciphertext:

K' = C XOR M'

Since the key is perfectly random, all these keys K' are equally likely. So all the plaintexts M' remain equally possible. The ciphertext makes it impossible to decide between any of them.

One ciphertext, all possible plaintexts

Suppose a ciphertext C = 1101 of 4 bits. Depending on the key, it could come from any 4-bit plaintext:

Observed ciphertext : C = 1101

If the key were…       …the plaintext would be  (M = C XOR K)
   K = 0000      ->      M = 1101   "could be this"
   K = 1011      ->      M = 0110   "or that"
   K = 1101      ->      M = 0000   "or even all zeros"
   K = 0110      ->      M = 1011   "or this again"
   ...                   ...        (16 plaintexts, all credible)

There are 2^4 = 16 possible keys, hence 16 possible plaintexts, all equally likely. Nothing in C points to the true one. The attacker is exactly as far along as before: they might just as well guess the message without looking at the ciphertext.

Unbreakable, even with infinite power

This is where the one-time pad distinguishes itself from all other encryption schemes. Against RSA or AES, an attacker with unlimited computing power would eventually test all the keys and recognize the right message. Here, no:

                Brute-force attack
                --------------------------------
  RSA / AES  :  all keys -> ONE sensible plaintext -> found
  OTP        :  all keys -> ALL plaintexts -> undecidable

Testing all the keys of the one-time pad does not produce one plaintext and garbage: it produces all possible messages, including all the sensible texts. It is impossible to know which one is the true one. Security does not depend on the adversary's power.

In summary

• Shannon (1949) defined perfect secrecy: the ciphertext reveals no information about the plaintext.
• The one-time pad achieves it: for every conceivable plaintext, there exists a key that leads to the same ciphertext, and all of them are equally likely.
• Consequence: it is unbreakable even with infinite computing power — brute force produces all the plaintexts at once.
• This is unconditional security, a unique case in cryptography. It remains to understand why we almost never use it.