The One-Time Pad: Perfect Secrecy

The One-Time Pad: Perfect Secrecy

The one-time pad (OTP) is the only known encryption scheme with perfect secrecy in the information-theoretic sense defined by Claude Shannon. That is a remarkable statement: no matter how much computing power an attacker has, they cannot extract any information about the plaintext from an OTP ciphertext.

Shannon's Definition of Perfect Secrecy

Claude Shannon proved in 1949 that an encryption scheme has perfect secrecy if and only if observing the ciphertext gives an attacker zero information about the plaintext. Formally:

P(plaintext = m | ciphertext = c) = P(plaintext = m)

In other words, seeing the ciphertext does not change your belief about what the plaintext might be. Every possible plaintext is equally consistent with every ciphertext.

How OTP Achieves This

The one-time pad works as follows:

The security argument: for any ciphertext C and any candidate plaintext M', there exists exactly one key K' = C XOR M' that would produce that ciphertext. Since all keys are equally probable (the key is truly random), all plaintexts are equally probable given any ciphertext.

The Three Requirements

OTP is perfectly secure only when three conditions are met:

1. The key is truly random. Pseudorandom keys (from a deterministic algorithm with a seed) do not give information-theoretic security. They give computational security, which is a weaker guarantee.

2. The key is at least as long as the message. This is a consequence of Shannon's theorem: any perfectly secure cipher must have a key space at least as large as the message space.

3. The key is used exactly once. If the same key is reused for two messages, an attacker can XOR the two ciphertexts together to get M1 XOR M2, which leaks information about both messages. (This attack was used to break Soviet OTP messages in the VENONA project.)