Perfect Secrecy and the One-Time Pad

Perfect secrecy is a property of an entire encryption scheme, defined over probability distributions rather than over specific messages. Fix a plaintext space $\mathcal{M}$, a ciphertext space $\mathcal{C}$, and a key space $\mathcal{K}$. Assume the key $K$ is drawn from some distribution (for the OTP, uniformly at random) independent of the message $M$, which itself is drawn from some distribution over $\mathcal{M}$ representing the adversary's prior beliefs. Encryption is a function $C = \mathrm{Enc}_K(M)$.

Definition (Shannon, 1949). An encryption scheme is perfectly secret if for every distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ with $\Pr[C = c] > 0$,

In words: observing the ciphertext changes nothing about the adversary's beliefs about the message. The posterior equals the prior. This is the cryptographic analogue of statistical independence between the random variables $M$ and $C$. An equivalent and often more convenient formulation is stated purely in terms of ciphertexts:

Equivalent definition. A scheme is perfectly secret iff for every two messages $m_0, m_1 \in \mathcal{M}$ and every ciphertext $c \in \mathcal{C}$,

where the probability is taken only over the choice of key $K$. This says the same ciphertext is produced with the same probability no matter which plaintext generated it — so seeing $c$ gives no way to distinguish which message was sent. This "indistinguishability" phrasing is exactly the ancestor of the computational indistinguishability games used later in Computational Security and the Adversary Model. The one-time pad is a concrete cipher over bit strings. Let $\mathcal{M} = \mathcal{C} = \mathcal{K} = \{0,1\}^n$. The key $K$ is sampled uniformly at random from $\{0,1\}^n$, independent of $M$, and:

where $\oplus$ denotes bitwise XOR. The scheme requires three conditions that are easy to state but hard to satisfy operationally: the key must be (1) truly random, (2) as long as the message, and (3) never reused for a second message. Violating any one of these destroys the security proof, not merely weakens it — a fact history has demonstrated expensively.

The mechanical procedure is almost embarrassingly simple compared to the depth of the proof it enables. The subtlety lives entirely in key management: generating true randomness, distributing it securely in advance, and guaranteeing it is destroyed after a single use. ``` // One-Time Pad — Setup (performed once, in advance, over a secure channel) function GenerateAndSharePad(n): K := SampleUniformRandomBits(n) // true randomness, e.g. physical entropy source send K to sender via secure out-of-band channel send K to receiver via secure out-of-band channel // both parties store K; it must never be reused or logged return K // Encryption function Encrypt(M, K): require length(M) == length(K) C := empty bit string for i := 1 to length(M): C[i] := M[i] XOR K[i] DestroyAfterUse(K) // mark this key material as spent return C // Decryption function Decrypt(C, K): require length(C) == length(K) M := empty bit string for i := 1 to length(C): M[i] := C[i] XOR K[i] DestroyAfterUse(K) return M ``` Correctness of decryption is immediate from the algebra of XOR: for every bit,

using associativity, commutativity, and the facts $K_i \oplus K_i = 0$ and $M_i \oplus 0 = M_i$. So $\mathrm{Dec}_K(\mathrm{Enc}_K(M)) = M$ always — this is perfect correctness, separate from and prerequisite to the perfect secrecy proof below. The architecture that makes this usable in practice — and the reason it is so rarely used — is shown below: the pad must be generated and physically transported before any message exists, then consumed bit-for-bit and never touched again.

Time and space complexity. Encryption and decryption are both $O(n)$ time and $O(n)$ additional space, where $n$ is the message length in bits — a single pass computing bitwise XOR, the cheapest possible operation on any architecture. There is no asymptotic overhead at all compared to sending the plaintext in the clear. The real cost is key material: the scheme consumes $n$ fresh, truly random key bits per message bit sent, and this key must be generated, transported, stored, and destroyed out of band. This is an $O(n)$ space and (usually) an $O(n)$ secure-channel-bandwidth cost, which for high-volume communication is the scheme's fatal practical flaw.

Correctness of decryption was shown above via the XOR self-inverse identity — this holds unconditionally, for every key and message, with probability 1.

Proof that the OTP is perfectly secret. Fix any message $m \in \{0,1\}^n$ and any ciphertext $c \in \{0,1\}^n$. Because $K$ is uniform over $\{0,1\}^n$ and independent of $M$,

Since $K$ is uniform over all $2^n$ strings, $\Pr[K = c \oplus m] = 1/2^n$ for every fixed $m$ and $c$ — the value $c \oplus m$ is just one particular string, and the uniform distribution assigns the same probability $1/2^n$ to every string. Hence

This value does not depend on $m$ at all. So for any two messages $m_0, m_1$,

which is exactly the ciphertext-indistinguishability form of perfect secrecy stated earlier. A short Bayes'-rule computation converts this into Shannon's original posterior-equals-prior form: since $\Pr[C=c \mid M=m] = 1/2^n$ is the same constant for every $m$,

because the constant $1/2^n$ cancels out of numerator and denominator entirely. $\blacksquare$ The intuitive reading of this proof: for every possible plaintext $m$, there is exactly one key that maps it to the observed ciphertext $c$ — namely $K = c \oplus m$ — and that key is exactly as likely as any other. Encryption under a uniform key is a bijection on $\{0,1\}^n$ for each fixed key, and averaging a bijection over a uniform key distribution produces a uniform, plaintext-independent ciphertext distribution. This bijection argument is the real engine of the proof and generalizes to any perfectly secret scheme over a group.

Shannon's impossibility theorem (key length lower bound). Perfect secrecy is not free — it forces $|\mathcal{K}| \geq |\mathcal{M}|$. Proof sketch. Suppose $|\mathcal{K}| < |\mathcal{M}|$. Fix any ciphertext $c$ that occurs with nonzero probability, and consider the set of plaintexts reachable from $c$ by some key: $S_c = \{ \mathrm{Dec}_k(c) : k \in \mathcal{K} \}$. Since decryption for each fixed key is a function, $|S_c| \leq |\mathcal{K}| < |\mathcal{M}|$. So there exists some plaintext $m^* \notin S_c$ — a message that no key at all can map to $c$. Then $\Pr[C = c \mid M = m^*] = 0$, while for a distribution assigning $m^*$ positive prior probability, perfect secrecy would require $\Pr[C = c \mid M = m^*] = \Pr[C=c] > 0$ whenever $\Pr[C=c]>0$ — a contradiction, since $0 \ne \Pr[C=c] > 0$. Hence no scheme with $|\mathcal{K}| < |\mathcal{M}|$ can be perfectly secret. $\blacksquare$ This means the one-time pad's key length — one full bit of key per bit of message — is not a naive or lazy design choice. It is provably optimal and unavoidable for any perfectly secret scheme. Every attempt to "compress" the key while keeping perfect secrecy is doomed by this counting argument; this is precisely the wall that motivates relaxing to computational security, covered in Limitations of Perfect Secrecy and Computational Security and the Adversary Model.

Honest tradeoffs. The OTP is unconditionally, information-theoretically secure — but only under three fragile assumptions: true (not pseudo-)randomness, one-time use, and secure prior key distribution of a length matching total future traffic. It provides no message authentication or integrity — an attacker who knows or guesses part of the plaintext can flip corresponding ciphertext bits to flip the plaintext bits, since XOR is malleable. It also provides no protection if the key is ever reused: XOR-ing two ciphertexts under the same key cancels the key entirely, $C_1 \oplus C_2 = M_1 \oplus M_2$, exposing the XOR of the two plaintexts — the exact failure mode that broke real Venona traffic.

Take a short ASCII message and trace both the encryption and the proof idea concretely. Let $M =$ `"HI"`, represented in binary (8-bit ASCII per character):

Concatenated plaintext:

Sample a truly random key of equal length (16 bits):

Compute $C = M \oplus K$ bit by bit:

So $C = 10011110\ 01110011$, which as bytes is `0x9E 0x73` — not printable ASCII, and structurally no different in appearance from the ciphertext of any other two-letter message.

Decryption, at the receiver, recomputes $C \oplus K$:

Correctly recovers `HI`.

Now the security argument, made concrete. Suppose an eavesdropper intercepts $C = 10011110\ 01110011$ and tries to guess whether $M$ was `"HI"` or some other message, say `"NO"` (`01001110 01001111`). For the adversary's guess to be consistent, there must exist a key $K'$ with $C = M' \oplus K'$:

This is a perfectly valid, equally likely 16-bit string — just as likely to have been the true key as the one that actually produced `"HI"`. Every candidate plaintext of the correct length is consistent with the observed ciphertext under some key, and every one of those keys is equally probable ($1/2^{16}$) under a uniform key distribution. The ciphertext therefore supplies zero evidence favoring `"HI"` over `"NO"` or any other 16-bit message — exactly the bijection argument from the proof above, instantiated on real bytes.

The one-time pad's engineering lineage traces to Gilbert Vernam, an AT&T engineer who patented a telegraph cipher combining plaintext with a random key stream in 1919, and to Joseph Mauborgne, who recognized that the key must be non-repeating and random to resist cryptanalysis. But the mathematical proof that such a scheme achieves absolute secrecy — and the very definition of perfect secrecy itself — came three decades later from Claude Shannon, whose 1949 paper "Communication Theory of Secrecy Systems" founded information-theoretic cryptography as a rigorous discipline.

Genuine one-time pads are used today only where key-distribution cost is acceptable relative to the value of absolute secrecy: certain diplomatic cables, some historical intelligence-agency communications, and specialized quantum key distribution deployments that use Quantum Key Distribution specifically to generate the fresh, truly random, shared key material an OTP needs. The core cryptographic lesson, however, permeates far beyond literal OTP use. Stream ciphers such as RC4 and the keystream generators inside AES-CTR mode are engineered as pseudorandom approximations of the one-time pad — same XOR-with-keystream structure, but with a short seed expanded computationally, trading Shannon's perfect guarantee for a computational one. Every proof of security for a modern stream cipher or block cipher mode implicitly measures itself against the OTP's ideal and asks how closely a computationally bounded adversary can be kept from distinguishing the real ciphertext from a true one-time-pad ciphertext. This comparison is the conceptual bridge into Computational Security and the Adversary Model, where the "any distribution, any adversary, forever" bar of perfect secrecy is relaxed to "no efficient adversary, with overwhelming probability" — the compromise that makes practical, scalable cryptography possible.

:::quiz[In the proof that OTP satisfies perfect secrecy, what key fact makes Pr[Enc_K(m) = c] independent of m?]

• The key is derived from the message using a hash function
• For any fixed m and c, exactly one key value c⊕m produces that ciphertext, and all keys are equally likely ✓
• The ciphertext space is smaller than the key space
• Encryption is a randomized, non-deterministic function of m alone

Ask the tutor: Why does relaxing "any adversary" to "any efficient adversary" let modern ciphers reuse short keys without violating Shannon's impossibility theorem?