1 Introduction
Communication Theory of Secrecy Systems (1949) is a landmark paper by Claude Shannon that applies the mathematical framework of information theory to cryptography. It provides a rigorous, probabilistic model for secrecy systems, defines the condition for perfect secrecy, and introduces information‑theoretic measures such as equivocation and unicity distance. This work is considered the foundation of modern theoretical cryptography, establishing the fundamental relationships among entropy, key size, and the resistance of ciphers to cryptanalysis.
1.1 Historical background
During and after World War II, Claude Shannon worked on both information theory and secure communications at Bell Laboratories. His 1948 paper “A Mathematical Theory of Communication” introduced entropy as a measure of information. The following year, he published the classified report “A Mathematical Theory of Cryptography” (later declassified and published as the present paper). The timing was significant: it united the nascent fields of information theory and cryptography, providing a common language for analyzing secrecy systems.
1.2 Scope and objectives
Shannon’s paper does not describe specific cipher algorithms; instead, it establishes theoretical bounds on what secrecy systems can achieve. It treats encryption as a probabilistic channel and analyzes the uncertainty (equivocation) of an adversary who intercepts ciphertext. The main objectives are to define perfect secrecy, to derive the necessary key size for such secrecy, and to introduce the concept of unicity distance as a measure of how much ciphertext is needed to uniquely determine the key.
2 Fundamental model of a secrecy system
Shannon proposes an abstract model consisting of a sender, a receiver, and an adversary, together with mathematical descriptions of encryption and decryption.
2.1 Sender, receiver, and adversary
The sender (Alice) wishes to transmit a secret message to the receiver (Bob) over an insecure channel. An adversary (Eve) can intercept the transmitted ciphertext. Shannon assumes that the adversary has complete knowledge of the encryption scheme except for the key.
2.2 Encryption and decryption functions
Let M be the set of possible plaintext messages, C the set of possible ciphertexts, and K the set of keys. The encryption function \(E_k: M \to C\) is a mapping for each key \(k \in K\). The decryption function \(D_k: C \to M\) satisfies \(D_k(E_k(m)) = m\) for all \(m \in M\). Both functions are assumed to be deterministic.
2.3 Key space and key selection
| The key space \(K\) is a finite set. The key is chosen according to a probability distribution, independent of the plaintext. In the simplest case, keys are chosen uniformly at random. The size of the key space, denoted \( | K | \), is a central parameter in the analysis. |
|---|
2.4 Probabilistic description of messages and keys
Plaintext messages are generated according to a known probability distribution \(P(M)\). For example, English text has a non‑uniform distribution of letters. The adversary knows this distribution. The key distribution \(P(K)\) is also known to the adversary (though the actual key is not). Together, these induce a joint distribution over plaintexts and ciphertexts.
3 Information‑theoretic quantities
Shannon uses entropy and its conditional variants to quantify uncertainty in secrecy systems.
3.1 Entropy of plaintext, ciphertext, and key
The entropy \(H(M)\) measures the average information content (in bits) of the plaintext. \(H(K)\) is the entropy of the key, and \(H(C)\) is the entropy of the ciphertext. If the key is uniformly random over \(N\) keys, then \(H(K) = \log_2 N\).
3.2 Conditional entropy (equivocation)
Conditional entropy, or *equivocation*, measures the adversary’s remaining uncertainty about the plaintext or key after observing the ciphertext.
3.2.1 Plaintext equivocation
| \(H(M | C)\) is the average uncertainty about the plaintext given the ciphertext. A higher value indicates greater secrecy; if \(H(M | C) = H(M)\), the ciphertext reveals nothing about the plaintext. |
|---|
3.2.2 Key equivocation
| \(H(K | C)\) measures the uncertainty about the key after seeing the ciphertext. This quantity is crucial for understanding the difficulty of key recovery. |
|---|
3.3 Joint and mutual information
| The mutual information \(I(M;C) = H(M) - H(M | C)\) quantifies the information leaked from plaintext to ciphertext. Perfect secrecy is equivalent to \(I(M;C)=0\). The joint entropy \(H(M,K,C)\) can also be used to express relationships among these quantities. |
|---|
4 Perfect secrecy
Perfect secrecy is the strongest notion of security: the ciphertext provides no information about the plaintext.
4.1 Definition and necessary conditions
| A secrecy system achieves perfect secrecy if for every plaintext \(m\) and every ciphertext \(c\), \(P(m | c) = P(m)\); equivalently, \(M\) and \(C\) are independent. |
|---|
4.1.1 Shannon’s condition for perfect secrecy
Shannon proves that a necessary and sufficient condition for perfect secrecy is that the number of keys is at least as large as the number of possible plaintexts, and that the key must be uniformly distributed over a set of size at least that number. More precisely, for each ciphertext \(c\), the mapping from keys to plaintexts must be invertible and every plaintext must be reachable by some key.
4.1.2 Relationship to key length
If plaintexts are binary strings of length \(n\) and keys are binary strings of length \(k\), perfect secrecy requires \(k \ge n\). In other words, the key must be at least as long as the plaintext.
4.2 The one‑time pad as an example
The one‑time pad (Vernam cipher) is the classic example of a perfect secrecy system. The plaintext, key, and ciphertext are all binary strings of equal length; encryption is bitwise XOR. If the key is chosen truly at random and never reused, perfect secrecy is achieved. Shannon’s analysis confirms that no shorter key can provide perfect secrecy.
4.3 Limitations of perfect secrecy
Perfect secrecy requires keys as long as the messages they protect, which is impractical for most real‑world applications. Key distribution and management become infeasible for large volumes of data. Moreover, perfect secrecy offers no protection against key reuse or against an adversary who can modify ciphertext (lack of integrity). These limitations motivate the study of computational security.
5 Redundancy and its role in cryptography
Natural languages contain redundancy—statistical patterns that make messages predictable. Shannon demonstrates that redundancy weakens secrecy systems.
5.1 Redundancy of natural languages
| The redundancy of a language is \(R = \log_2 | M | - H(M)\), where \( | M | \) is the number of possible messages of a given length. For English, this redundancy is estimated to be about 50–75%. Redundancy allows an adversary to narrow down possible plaintexts. |
|---|
5.2 Unicity distance
Shannon introduces the *unicity distance*—the minimum amount of ciphertext needed to uniquely determine the key, assuming infinite computational power.
5.2.1 Derivation from equivocation
| The unicity distance \(U\) can be derived from the equivocation function \(H(K | C)\). As more ciphertext is observed, \(H(K | C)\) decreases. The unicity distance is the point at which \(H(K | C) \approx 0\). For an ideal cipher with uniformly random keys, it is approximately \(U \approx \frac{H(K)}{R}\), where \(R\) is the redundancy per letter. |
|---|
5.2.2 Practical meaning for cipher strength
A cipher with a large unicity distance is resistant to brute‑force attacks based on ciphertext‑only analysis. For example, the unicity distance of a substitution cipher for English is about 25–30 letters. Beyond this length, a unique correct decryption exists (in theory). Modern ciphers like AES have unicity distances much larger than any realistic message length, making them information‑theoretically secure against ciphertext‑only attacks.
6 The random cipher model
To analyze the average behavior of ciphers, Shannon introduces the *random cipher* model—an idealized abstraction that approximates real block ciphers.
6.1 Definition of a random cipher
A random cipher is a family of enciphering transformations on the set of possible messages (of fixed length) such that, for a given key, the ciphertext is a random permutation of the message space. All permutations are equally likely and independent of the key. This model captures the idea that a good cipher should appear to be a random mapping.
6.2 Equivocation characteristic for a random cipher
Under the random cipher model, the equivocation functions behave in a predictable way as the amount of ciphertext increases.
6.2.1 Idealized behavior
| The plaintext equivocation \(H(M | C)\) starts at \(H(M)\) and remains high until the unicity distance, after which it drops sharply to zero. Similarly, \(H(K | C)\) remains nearly constant at \(H(K)\) until near the unicity distance, then falls rapidly. This "cliff‑edge" behavior is the idealized characteristic. |
|---|
6.2.2 Comparison with real ciphers
Real ciphers often show a more gradual decline in equivocation, especially if they have structural weaknesses (e.g., linear or differential properties). Shannon notes that the random cipher model provides a benchmark for evaluating the security of real systems: a cipher is “good” if its equivocation characteristic is close to the random ideal.
6.3 The concept of break‑even point
The break‑even point is the length of ciphertext for which the effort of cryptanalysis equals the expected benefit. Shannon suggests that for practical purposes, a cipher should be designed such that the unicity distance exceeds any feasible message length, thereby making exhaustive search the only option.
7 Applications and extensions
Shannon’s work has had profound and lasting impact on cryptography and information theory.
7.1 Computational versus theoretical security
Shannon’s framework is information‑theoretic: it assumes the adversary has unlimited computational power. Modern cryptography often relies on computational security, where breaking a cipher is merely computationally infeasible. The distinction is central: perfect secrecy is information‑theoretic, while practical ciphers (e.g., AES) are computationally secure. Shannon’s contribution provides the theoretical upper bound that computational security cannot exceed.
7.2 Influence on later cryptographic design
The concepts of key entropy, redundancy, and unicity distance directly influenced the design of block ciphers (e.g., the substitution–permutation network) and the development of stream ciphers. Shannon’s call for confusion and diffusion (though not explicitly in this paper but in related work) became design principles. The analysis also led to the understanding that good ciphers must destroy redundancy through diffusion and non‑linear substitution.
7.3 Role in modern information‑theoretic security
Modern fields such as quantum key distribution and physical‑layer security build directly on Shannon’s framework. The concept of equivocation is used to derive capacity bounds for wiretap channels. The one‑time pad remains the canonical example of perfectly secure communication, and Shannon’s impossibility result (no perfect secrecy with shorter keys) is a fundamental law.