The Math Behind the One-Time Pad's Perfect Secrecy

This article explains why the one-time pad (OTP) is the only encryption method mathematically proven to achieve perfect secrecy. By exploring Claude Shannon's information theory, this overview breaks down how true randomness, key length, and single-use constraints make it impossible for an attacker to extract any information about a plaintext message from its ciphertext, regardless of their computational power.

Defining Perfect Secrecy

In 1949, mathematician Claude Shannon founded information theory and established the mathematical definition of "perfect secrecy." According to Shannon, an encryption scheme has perfect secrecy if an intercepted ciphertext provides an attacker with zero information about the original plaintext message (other than its maximum possible length).

In probability terms, the probability of a specific message existing before the attacker intercepts the ciphertext must be the exact same as the probability of that message existing after they intercept it. Knowing the ciphertext does not help the attacker narrow down the possibilities at all.

How the One-Time Pad Works

The one-time pad is a symmetric encryption algorithm that combines a plaintext message with a random secret key (the "pad"). In modern computing, this is done using the bitwise XOR (exclusive OR) operation.

  1. The plaintext is converted into bits (0s and 1s).
  2. A truly random key of the exact same bit-length is generated.
  3. Each bit of the plaintext is combined with the corresponding bit of the key to produce the ciphertext.

To decrypt the message, the recipient applies the exact same key to the ciphertext using the XOR operation, revealing the original plaintext.

The Information-Theoretic Proof

Most modern encryption, such as AES or RSA, relies on computational security. These systems are secure only because current computers would take billions of years to guess the key. However, if an attacker had infinite computing power, they could easily break AES by testing every possible 256-bit key until a readable message appeared.

The one-time pad relies on information-theoretic security, which holds up even against an attacker with infinite computing power.

Imagine an attacker intercepts a 5-letter OTP-encrypted ciphertext: XMCKL. The attacker uses a supercomputer to try every possible 5-letter key to decrypt it. In doing so, the computer will successfully generate every possible 5-letter word in the English language. It will produce HELLO, PEACE, WATER, and ZEBRA, along with millions of random letter combinations.

Because the key was generated with true randomness (a uniform probability distribution), every single possible key was equally likely to be used. Consequently, every possible 5-letter plaintext message is equally likely to be the correct one. The attacker has no mathematical way to know if the original word was HELLO or WATER. The randomness of the key completely absorbs and hides the statistical patterns of the plaintext.

Why No Other Scheme Can Achieve This

The one-time pad is the only encryption scheme capable of perfect secrecy because of Shannon's Theorem.

Shannon proved that for any encryption system to have perfect secrecy, the number of possible keys must be at least as large as the number of possible messages. This means the key must always be at least as long as the message itself.

If a key is shorter than the message (as is the case in all modern standard encryption like AES), the number of possible keys is smaller than the number of possible messages. An attacker with infinite computing power could try all keys, eliminate the massive number of impossible plaintexts that cannot be generated by those keys, and identify the one valid plaintext that makes linguistic sense.

Any encryption scheme that meets Shannon's requirement—using a truly random key, at least as long as the message, only once—is, by definition, a one-time pad or a direct mathematical equivalent of it.

The Four Strict Rules of the One-Time Pad

The mathematical proof of the one-time pad instantly collapses if human error or system limitations violate any of its four strict rules:

  • The key must be truly random: Computer-generated pseudo-random numbers have underlying mathematical patterns. True randomness requires physical phenomena, such as radioactive decay or atmospheric noise.
  • The key must be at least as long as the plaintext: If the key is shorter, the system falls back to computational security.
  • The key must never be reused: Hence the name "one-time" pad. If a key is used twice for two different messages, an attacker can XOR the two ciphertexts together. This cancels out the key entirely and leaves the attacker with the XOR combination of the two plaintexts, which can be easily cracked using frequency analysis.
  • The key must be kept completely secret: If an attacker obtains the key, the encryption is useless.