Perfect Secrecy, One-Time Pad Encryption, and Characterizations of Perfect Secrecy

Definition

A cryptosystem has perfect secrecy if observing the ciphertext gives no information about the plaintext.

Formally, if M is a message random variable and C is the ciphertext random variable, then perfect secrecy means:

$$P(M=m \mid C=c) = P(M=m)$$

for every message m and ciphertext c such that P(C=c) > 0.

This says that the posterior probability of any message after seeing the ciphertext is exactly the same as the prior probability before seeing it.

A closely related equivalent form is:

$$P(C=c \mid M=m_1) = P(C=c \mid M=m_2)$$

for all messages m_1, m_2 and ciphertexts c.
This means that the ciphertext distribution does not depend on which message was encrypted.

The one-time pad is a symmetric encryption method where:

• the key is truly random,
• the key length is equal to the message length,
• encryption is performed using bitwise XOR or modular addition,
• the key is used only once.

For binary messages, the OTP encryption rule is:

$$C = M \oplus K$$

where:

• M = plaintext,
• K = random key,
• C = ciphertext,
• \oplus = XOR operation.

---

Main Content

1. Perfect Secrecy

Meaning and intuition

Perfect secrecy means that ciphertext reveals no statistical information about the plaintext. Even if an attacker knows the encryption algorithm, the ciphertext, and all details except the key, they still cannot improve their guess about the message. In other words, ciphertext should not reduce uncertainty about the plaintext.

Example: Suppose a message is either "YES" or "NO" with equal probability. If an encryption scheme is perfectly secret, then after seeing the ciphertext, the attacker’s belief about whether the original message was "YES" or "NO" remains unchanged.

Mathematical characterization

The defining condition is: $$P(M=m \mid C=c) = P(M=m)$$ for all valid m and c.
Using Bayes’ rule, this is equivalent to: $$P(C=c \mid M=m) = P(C=c)$$ for all m, c, which says the ciphertext distribution is independent of the plaintext. This independence is the core idea behind perfect secrecy.

Another useful viewpoint is mutual information: $$I(M;C)=0$$ meaning the plaintext and ciphertext share no information.

ASCII diagram for intuition

Plaintext M  ----encrypt with secret key---->  Ciphertext C
     |                                            |
     |                                            |
     +---------- attacker sees C ------------------+

Perfect secrecy means: seeing C does not change what can be inferred about M.

2. One-Time Pad Encryption

Construction

The one-time pad uses a key that is:

1. random,
2. the same length as the message,
3. secret,
4. never reused.

For a binary message M = (m1, m2, ..., mn) and key K = (k1, k2, ..., kn), encryption is: $$C_i = M_i \oplus K_i \quad \text{for } i=1,2,\dots,n$$ Decryption uses the same operation: $$M_i = C_i \oplus K_i$$ because XOR is its own inverse.

Why it achieves perfect secrecy

If the key is uniformly random over all possible keys of the same length as the message, then for any plaintext m and any ciphertext c, there is exactly one key k = m \oplus c that produces c from m. Since every key is equally likely, every ciphertext is equally likely for every plaintext. Therefore: $$P(C=c \mid M=m) = P(K=m \oplus c)$$ and this probability is the same for all m.

Example: If the message is 1011 and the key is 0110, then the ciphertext is: $$1011 \oplus 0110 = 1101$$ Anyone who sees 1101 without the key cannot determine whether the original plaintext was 1011, 0000, or any other 4-bit string, because every plaintext is compatible with some equally likely key.

Strict requirements and limitations

The one-time pad is perfectly secure only if the key is:

• truly random,
• as long as the message,
• kept completely secret,
• never reused.

If the same key is reused even once, security breaks badly. For two messages M1 and M2 encrypted with the same key K: $$C_1 = M_1 \oplus K,\quad C_2 = M_2 \oplus K$$ then: $$C_1 \oplus C_2 = M_1 \oplus M_2$$ which reveals a direct relationship between the two plaintexts.

3. Characterizations of Perfect Secrecy

Equivalent definitions

Perfect secrecy can be described in several equivalent ways:

1. Posterior equals prior $$P(M=m \mid C=c) = P(M=m)$$

2. Ciphertext independent of plaintext $$P(C=c \mid M=m) = P(C=c)$$

3. Message distributions identical for all plaintexts $$P(C=c \mid M=m_1) = P(C=c \mid M=m_2)$$

4. Zero mutual information $$I(M;C)=0$$

These are all saying the same thing in different mathematical language.

Shannon’s characterization and key-space requirement

Claude Shannon showed that for perfect secrecy:

• the key space must be at least as large as the message space,
• and the key entropy must be at least the message entropy.

In particular, if the message space has size |M|, then the key space must satisfy: $$|K| \ge |M|$$ and for ideal perfectly secret systems: $$H(K) \ge H(M)$$

This is a major practical limitation: perfect secrecy requires a lot of randomness.

Consequences of perfect secrecy

If a scheme is perfectly secret:

• no ciphertext pattern can favor one message over another,
• the attacker cannot do better than guessing based on prior probabilities,
• the encryption algorithm may be public, but security rests entirely on the key.

Example: If messages "attack" and "retreat" are equally likely, then after seeing the ciphertext, the attacker still believes each is equally likely. The ciphertext does not change that belief.

---

Working / Process

1. Generate a truly random key

• The key must be unpredictable and uniformly random.
• Its length must match the message length exactly.
• For OTP, every bit or symbol of the key must be independent.

2. Encrypt the message

• Combine plaintext and key using XOR for binary data or modular addition for alphabetic/numeric systems.

• Example for binary: $$C = M \oplus K$$

• Example for 26-letter alphabet: $$c_i = (m_i + k_i) \bmod 26$$

3. Decrypt using the same key

• Apply the same operation again: $$M = C \oplus K$$

• The original message is recovered exactly.

• After use, the key must be destroyed and never reused.

---

Advantages / Applications

Provable strongest confidentiality

• Perfect secrecy gives a mathematically exact security guarantee.
• It is not based on computational hardness assumptions.

Useful as a theoretical benchmark

• It defines the ideal against which other encryption systems are compared.
• It helps students understand why modern cryptography usually settles for computational security.

Important in high-security communication scenarios

• The OTP has been historically used where absolute confidentiality was needed and key distribution was feasible.
• It is also valuable in teaching, proofs, and cryptographic theory.

---

Summary

• Perfect secrecy means ciphertext gives no information about plaintext.
• The one-time pad achieves perfect secrecy when the key is truly random, as long as the message, and never reused.
• Perfect secrecy can be characterized by equivalence of prior and posterior probabilities, independence of plaintext and ciphertext, or zero mutual information.
• A very small definition: perfect secrecy is “no leakage of message information from ciphertext.”