Shannon ciphers, one-time pads, and perfect secrecy

Updated 05 Nov 2026

• •

  Formal Shannon ciphers

  • •

    

  • •

    Definition

    • •

      a Shannon cipher is a pair of functions $\mathcal{E} = (E, D)$ defined over $(K, M, C)$:

      • •

        $K$ -> key spcae (set of all possible secret keys)

      • •

        $M$ -> message space (set of all valid plaintexts)

      • •

        $C$ -> ciphertext space (set of all possible encrypted otuputs)

      • •

        Encryption function -> $E: K \times M \to C$

      • •

        Decryption function -> $D: K \times C \to M$

  • •

    Correctness requirement

    • •

      for all keys $k \in K$ and all messages $m \in M$:

      • •
        $$D(k, E(k, m)) = m$$
    • •

      decryption under the correct key must unambiguously invert encyrption

  • •

    Theoretical nature -> defined purely as mathematical functions; does not enforce polynomial-time computation efficiency

• •

  The One-Time Pad (Vernam 1917)

  • •

    Definition

    • •

      the canonical construction of a Shannon cipher, invented by Gilbert Vernam in 1917

    • •

      Plaintext, ciphertext, and key spaces are bit strings of identical fixed length $L$:

      • •
        $$K = M = C = \{0, 1\}^L$$
    • •

      the key $k$ is sampled uniformly from $\{0, 1\}^L$: $k \xleftarrow{R} \{0, 1\}^L$.

  • •

    Operations

    • •

      Encryption -> bitwise XOR of key and message:
      $$c = E(k,m) := k \oplus m$$

    • •

      Decryption -> bitwise XOR of key and ciphertext

      • •
        $$m = D(k,m) := k \oplus c$$
  • •

    Self-inverting correctness

    • •

      follows directly from the algebraic involution of XOR ($x \oplus x = 0$ and $x \oplus 0 = x$):

      • •
        $$D(k, E(k, m)) = k \oplus (k \oplus m) = (k \oplus k) \oplus m = 0 \oplus m = m$$
  • •

    OTP variants

    • •

      Variable-length pad -> keys of fixed length $L$, messages up to length $L$ encrypted with a truncated key prefix. This variant leaks plaintext length because $|c| = |m|$, violating perfect security.

    • •

      Additive OTP -> defined over integers $\{0, \dots, n-1\}$ using addition modulo $n$: $E(k, m) = (k + m) \pmod n$ and $D(k, c) = (c - k) \pmod n$. Perfectly secure.

    • •

      Multiplicative OTP -> defined over field $\{1, \dots, p-1\}$ for prime $p$ using modular multiplication: $E(k, m) = (k \cdot m) \pmod p$ and $D(k, c) = (c \cdot k^{-1}) \pmod p$. Perfectly secure.

  • •

    Trivial key recovery

    • •

      handed both plaintext $m$ and ciphertext $c$, the key is computed instantly: $k = m \oplus c$

    • •

      emphasizes why keys must never be reused across multiple messages (see Two-Time Pad attack)

  • •

    Practical limitations

    • •

      Key distribution dilemma -> the secret key must be as long as the message. If a secure channel exists to transfer an $L$-bit key, Alice and Bob could simply transmit the $L$-bit message itself

    • •

      Lack of integrity -> Bit flips in the ciphertext produce direct, predictable bit flips in the decrypted plaintext (see Malleability)

• •

  Perfect security (Shannon 1949)

  • •

    Formal definition

    • •

      cipher $\mathcal{E} = (E, D)$ over $(K, M, C)$ possesses perfect security if for all messages $m_0, m_1 \in M$ and all ciphertexts $c \in C$:

      • •
        $$\Pr_{k \xleftarrow{R} K}[E(k, m_0) = c] = \Pr_{k \xleftarrow{R} K}[E(k, m_1) = c]$$
    • •

      seeing ciphertext $c$ provides an eavesdropper with zero information about which plaintext was transmitted

  • •

    Equivalent characterizations

    • •

      Bipartite key balance -> for every ciphertext $c$, the count of distinct keys mapping $m_0$ to $c$ exactly equals the count of keys mapping $m_1$ to $c$.

    • •

      Indistinguishable predicates -> for every decision predicate $\phi: C \to \{0,1\}$:

      • •
        $$\Pr[M = m \mid C = c] = \Pr[M = m]$$
    • •

      Statistical independence -> the random variables for plaintext $M$ and ciphertext $C$ are independent

  • •

    Proof that the One-Time Pad is perfectly secure

    • •

      for any fixed message $m \in \{0, 1\}^L$ and any fixed ciphertext $c \in \{0, 1\}^L$, the equation $k \oplus m = c$ has exactly one unique solution: $k = m \oplus c$.

    • •

      because key $k$ is drawn uniformly from $\{0, 1\}^L$:

      • •
        $$\Pr_{k \xleftarrow{R} K}[E(k, m) = c] = \Pr_{k \xleftarrow{R} K}[k = m \oplus c] = \frac{1}{|K|} = \frac{1}{2^L}$$
    • •

      since this probability is $1/2^L$ for every message $m$, $\Pr[E(k, m_0) = c] = \Pr[E(k, m_1) = c] = 1/2^L$ holds universally.

  • •

    

• •

  Shannon's Theorem and the limits of perfect secrecy

  • •

    Theorem statement

    • •

      if a Shannon cipher $\mathcal{E} = (E, D)$ over $(K, M, C)$ is perfectly secure, then the key space must be at least as large as the message space:

      • •
        $$|K| \ge |M|$$
    • •

      for fixed-length binary strings where $|K| = 2^k$ and $|M| = 2^m$, this implies key length must satisfy:

      • •
        $$\operatorname{len}(k) \ge \operatorname{len}(m)$$
  • •

    Proof by contradiction

    • •

      assume $|K| < |M|$

    • •

      fix an arbitrary valid ciphertext $c \in C$

    • •

      consider the set of all possible plaintexts that can result from decrypting $c$ under all valid keys:

      • •
        $$S_c := \{ D(k, c) \mid k \in K \}$$
    • •

      because each key produces at most one plaintext, $|S_c| \le |K| < |M|$

    • •

      therefore, there exists at least one message $m^* \in M$ such that $m^* \notin S_c$

    • •

      for this message $m^*$, it can never encrypt to $c$ under any key:

      • •
        $$\Pr_{k \xleftarrow{R} K}[E(k, m^*) = c] = 0$$
    • •

      however, for any message $m \in S_c$, there exists at least one key $k$ where $E(k, m) = c$, meaning:

      • •
        $$\Pr_{k \xleftarrow{R} K}[E(k, m) = c] > 0$$
    • •

      this creates an inequality $\Pr[E(k, m) = c] \neq \Pr[E(k, m^*) = c]$, directly violating the definition of perfect security. contradiction

  • •

    Significance for modern cryptography

    • •

      establishes that perfect security is practically unachievable for real-world data systems (encrypting a 10 GB database requries a pre-shared 10 GB key)

    • •

      derives the shift from information-theoretic security to computational ciphers, trading absolute mathematical impossibility for computational intractability against polynomial-time adversaries

◌ Explore connections in Graph view