Perfect secrecy - Ciallo Wiki

Perfect secrecy, also known as information-theoretic security, is a property of cryptographic systems wherein the ciphertext reveals no information about the plaintext, even to an adversary with unlimited computational power. Formally introduced by Claude Shannon in his 1949 paper "Communication Theory of Secrecy Systems," it is defined by the condition that the probability distribution of the plaintext is independent of the ciphertext. The classic example achieving perfect secrecy is the one-time pad, which requires a key at least as long as the message, used only once, and drawn uniformly at random. Perfect secrecy is the strongest notion of confidentiality, but its practicality is limited by key management constraints.

1 Definition and Core Concepts

1.1 Information-Theoretic Security

Information-theoretic security refers to cryptographic guarantees that hold regardless of the adversary’s computational resources. Unlike computational security, which assumes bounded computing power, information-theoretic security relies solely on probability theory and information theory. A scheme is information-theoretically secure if the ciphertext does not reveal any statistical information about the plaintext.

1.1.1 Entropy and Conditional Entropy

Entropy, denoted \(H(X)\), measures the uncertainty of a random variable \(X\). Conditional entropy \(H(X	Y)\) quantifies the remaining uncertainty about \(X\) after observing \(Y\). In perfect secrecy, the conditional entropy of the plaintext given the ciphertext equals the entropy of the plaintext: \(H(P	C) = H(P)\), meaning the ciphertext provides zero reduction in uncertainty.

1.2 Shannon's Formalization

Shannon gave a precise mathematical framework for secrecy. He modeled a cryptosystem as a mapping from plaintexts and keys to ciphertexts, with probability distributions over plaintexts and keys.

1.2.1 Perfect Secrecy Condition: \(P(\text{Plaintext}|\text{Ciphertext}) = P(\text{Plaintext})\)

The defining condition for perfect secrecy is that for every plaintext \(m\) and ciphertext \(c\), \(\Pr(P = m \mid C = c) = \Pr(P = m)\). This means the ciphertext gives no information to modify the a priori probability of any plaintext.

1.2.2 Equivalence to Zero Mutual Information

The condition above is equivalent to the mutual information between plaintext and ciphertext being zero: \(I(P; C) = 0\). Since mutual information is always non-negative, zero indicates complete independence. Thus perfect secrecy is an information-theoretic notion of independence.

2 Achieving Perfect Secrecy

2.1 One-Time Pad

The one-time pad (OTP) is the quintessential perfectly secret cipher. It was invented by Frank Miller and later patented by Gilbert Vernam. In the OTP, the plaintext is XORed with a key of the same length, producing a ciphertext. Decryption applies the same XOR.

2.1.1 Key Requirements: Length, Randomness, and Single Use

For perfect secrecy, the key must be at least as long as the plaintext, generated uniformly at random from all possible sequences, and used exactly once. Reuse of a key or using non-uniform randomness breaks the secrecy guarantee.

2.1.2 Proof of Perfect Secrecy

Given a uniform random key \(K\) independent of plaintext \(P\), for any fixed ciphertext \(c\), \(\Pr(C = c) = 1/2^n\) (assuming \(n\)-bit messages). For any \(m\), \(\Pr(P = m \mid C = c) = \frac{\Pr(K = m \oplus c) \Pr(P = m)}{\Pr(C = c)} = \frac{(1/2^n) \Pr(P = m)}{1/2^n} = \Pr(P = m)\). Thus perfect secrecy holds.

2.2 Other Perfectly Secret Schemes

2.2.1 Vernam Cipher (extension)

The Vernam cipher is historically the same as the one-time pad when used with binary data. In a broader sense, Vernam’s original electromechanical system used a teletypewriter and a random tape. It is considered a direct implementation of perfect secrecy.

2.2.2 Quantum Key Distribution (conceptual link)

Quantum key distribution (QKD) protocols, such as BB84, allow two parties to generate a shared random key with information-theoretic security based on quantum mechanical principles. Although QKD does not itself encrypt messages, it provides a key that can be used in a one-time pad, enabling end-to-end perfect secrecy. The security derives from the no-cloning theorem and the disturbance caused by eavesdropping.

3 Limitations and Practical Considerations

3.1 Key Length and Key Distribution Problem

Perfect secrecy requires a key at least as long as the total amount of plaintext. This creates a key distribution problem: two parties must share a large, random secret before communication. Distributing such keys securely over distance is often as difficult as transmitting the plaintext itself.

3.2 Impracticality for Large-Scale Communication

For bulk encryption (e.g., streaming video or large databases), the one-time pad’s key size becomes prohibitive. Modern networks use computationally secure ciphers with short keys (e.g., AES) that are practical for high‑volume communication. Perfect secrecy is thus limited to small or highly sensitive messages.

3.3 Relationship to Computational Security

3.3.1 Comparison with Semantic Security

Semantic security is the computational analog of perfect secrecy. It guarantees that any efficient adversary cannot learn any partial information about the plaintext from the ciphertext. Unlike perfect secrecy, semantic security allows an arbitrarily small probability of information leakage and relies on hardness assumptions. The two concepts coincide in the ideal case of unlimited resources.

3.3.2 Trade-offs: Perfect vs. Practical Secrecy

Perfect secrecy offers unconditional guarantees but at the cost of key management overhead. Computational security provides practicality (short keys, efficient encryption) but relies on unproven assumptions (e.g., the difficulty of factoring). In most real‑world applications, the trade‑off favors computational security, reserving perfect secrecy for scenarios where absolute confidentiality is paramount.

4.1 Entropy-Based Lower Bounds

4.1.1 Shannon's Lower Bound on Key Size

Shannon proved that for any perfectly secret system, the key entropy must be at least as large as the plaintext entropy. This follows from the conditional entropy inequality: \(H(K) \ge H(P)\). Thus no scheme can achieve perfect secrecy with a key shorter than the plaintext (in the sense of entropy).

4.1.2 Necessary Condition: \(H(K) \ge H(P)\)

The inequality \(H(K) \ge H(P)\) is both necessary and sufficient for the existence of a perfectly secret cipher when the key and plaintext are independent. It formalizes the intuition that the key must introduce enough randomness to mask the plaintext.

4.2 Perfect Secrecy for Multiple Messages

4.2.1 Shannon's Negative Result (Impossibility for Multiple Encryptions)

Shannon showed that if multiple messages are encrypted with the same key, perfect secrecy is impossible unless the key length is at least the sum of the message lengths. More precisely, using the same key for two or more encryptions inevitably leaks information unless each new message extends the key. This result underscores the “one‑time” nature of perfect secrecy.

4.3.1 Perfectly Secure Authentication Codes

An authentication code provides information‑theoretic security against forgeries if the probability that an adversary can create a valid tag (MAC) is exactly \(1/	\mathcal{T}	\) (where \(\mathcal{T}\) is the tag space). Such codes exist, e.g., using universal hash families, and offer unconditional integrity guarantees analogous to perfect secrecy.

Shamir’s secret sharing divides a secret into shares such that any \(t\) shares reconstruct the secret, but any \(t-1\) shares reveal no information about it. This property is information‑theoretic: the shares carry zero mutual information with the secret unless enough shares are combined. It is a form of perfect secrecy applied to distributed trust.