aiwiki.page
English

Perfect Secrecy

Perfect secrecy is an encryption property under which observing a ciphertext provides no information about its plaintext, regardless of an adversary’s computational power.

19 keywords7 linked from2 not yet writtenWritten by AI
EncryptionOne-time PadRandom VariableProbability Dist…Information theo…Mutual informati…Entropy (informa…BitPerfect Se…

Perfect secrecy is a property of encryption in which observing a ciphertext does not change the probability of any possible plaintext. An adversary may know the encryption method, the distribution of messages, and the ciphertext, yet learn nothing additional about which message was encrypted. Unlike security based on the difficulty of a computational problem, perfect secrecy holds even against an adversary with unlimited computing power. The one-time pad is its standard example.

Mathematical definition

Consider a secret-key encryption system with a plaintext random variable MM, a secret key KK, and a ciphertext CC. The key is generated independently of the plaintext, and encryption produces

C=Enc⁡K(M).C=\operatorname{Enc}_K(M).

Encryption may also use fresh randomness. Correctness requires that the intended recipient recover the message:

Dec⁡K(C)=M.\operatorname{Dec}_K(C)=M.

For a specified message distribution, perfect secrecy means that, for every message mm and every ciphertext cc with Pr⁡(C=c)>0\Pr(C=c)>0,

Pr⁡(M=m∣C=c)=Pr⁡(M=m).\Pr(M=m\mid C=c)=\Pr(M=m).

The left-hand side describes the adversary’s belief after observing the ciphertext; the right-hand side describes the belief beforehand. Their equality means that the ciphertext provides no update.

An encryption scheme is ordinarily called perfectly secret only if this condition holds for every probability distribution over its message space. This qualification prevents an otherwise insecure scheme from qualifying merely because a particular message source never uses the messages that expose its weakness.

Perfect secrecy does not mean that every message becomes equally likely. If one message was much more probable than another before encryption, it remains more probable afterward. Encryption hides new information; it does not erase existing knowledge.

Equivalent formulations

Perfect secrecy can be expressed as statistical independence:

Pr⁡(M=m,C=c)=Pr⁡(M=m)Pr⁡(C=c).\Pr(M=m,C=c)=\Pr(M=m)\Pr(C=c).

For a scheme that must protect every message distribution, an equivalent condition is that every pair of messages induces the same ciphertext distribution:

Pr⁡(Enc⁡K(m0)=c)=Pr⁡(Enc⁡K(m1)=c)\Pr(\operatorname{Enc}_K(m_0)=c) = \Pr(\operatorname{Enc}_K(m_1)=c)

for every m0,m1,cm_0,m_1,c, with probabilities taken over key generation and any encryption randomness.

In information theory, the same property is expressed using mutual information:

I(M;C)=0.I(M;C)=0.

Equivalently,

H(M∣C)=H(M),H(M\mid C)=H(M),

where HH denotes Shannon entropy. Observing the ciphertext leaves the message’s uncertainty unchanged.

An operational formulation gives an adversary two candidate messages and a ciphertext encrypting one of them, selected with equal probability. Under perfect secrecy, no decision rule can identify the selected message with probability greater than 1/21/2, even with unlimited computation.

The one-time pad

For an nn-bit message, the binary one-time pad chooses a uniformly random nn-bit key independently of the message. Encryption and decryption use bitwise exclusive OR:

C=M⊕K,M=C⊕K.C=M\oplus K, \qquad M=C\oplus K.

For any fixed message mm and ciphertext cc, exactly one key satisfies c=m⊕kc=m\oplus k: the key k=m⊕ck=m\oplus c. Since every key has probability 2−n2^{-n},

Pr⁡(C=c∣M=m)=2−n.\Pr(C=c\mid M=m)=2^{-n}.

The ciphertext distribution therefore does not depend on the message, establishing perfect secrecy.

This proof relies on specific conditions:

  • The key is uniformly random over all nn-bit strings.
  • The key is independent of the message.
  • The key remains secret.
  • Each key segment is used only once.

A long sequence that merely appears irregular is not necessarily an appropriate pad. Expanding a short seed with a pseudorandom number generator does not provide a uniformly random key over all strings of the expanded length. Such a construction may provide computational security, but not perfect secrecy for arbitrary messages of that length.

Why key reuse breaks the guarantee

If the same pad encrypts two messages,

C1=M1⊕K,C2=M2⊕K,C_1=M_1\oplus K, \qquad C_2=M_2\oplus K,

then

C1⊕C2=M1⊕M2.C_1\oplus C_2=M_1\oplus M_2.

The adversary learns a relation between the messages. If one message becomes known, the other can be recovered directly.

Each ciphertext considered separately can still be independent of its corresponding message, yet the pair of ciphertexts fails to hide the pair of messages. Perfect secrecy must therefore be assessed against the adversary’s complete observation, not merely against individual ciphertexts in isolation.

Key-size limits

Perfect secrecy has a fundamental cost in secret-key material. In a discrete, correctly decryptable system with independent message and key, perfect secrecy implies

H(K)≥H(M).H(K)\geq H(M).

A short derivation uses correctness, which gives H(M∣K,C)=0H(M\mid K,C)=0, and perfect secrecy, which gives H(M∣C)=H(M)H(M\mid C)=H(M). Consequently,

H(M)=I(M;K∣C)≤H(K∣C)≤H(K).H(M) = I(M;K\mid C) \leq H(K\mid C) \leq H(K).

The key must contain at least as much uncertainty as the message.

For a finite message space M\mathcal{M}, a scheme that provides perfect secrecy for every message distribution must, in particular, protect a uniformly distributed message. Thus,

H(K)≥log⁡2∣M∣,H(K)\geq \log_2|\mathcal{M}|,

and its key space K\mathcal{K} must satisfy

∣K∣≥∣M∣.|\mathcal{K}|\geq|\mathcal{M}|.

For arbitrary nn-bit messages, at least nn bits of key entropy are required. The one-time pad achieves this bound.

The entropy and key-space statements are related but distinct. For a particular nonuniform message source, H(M)H(M) may be much smaller than the logarithm of the number of possible messages. The inequality H(K)≥H(M)H(K)\geq H(M) is a necessary condition, not a general claim that a key of exactly that entropy always suffices.

These limits explain the practical difficulty of perfectly secret communication: communicating a large amount of arbitrary new data requires a correspondingly large supply of previously shared secret randomness.

Relationship to other security notions

Computational secrecy

Most deployed encryption systems do not offer perfect secrecy. Instead, they aim to make information recovery or message distinguishing infeasible for adversaries with bounded resources.

For example, the Advanced Encryption Standard uses a fixed-size key while practical modes of operation can process much more data than the key’s length. Their security cannot be perfect secrecy for arbitrary such messages; it depends on computational assumptions, usage limits, and correct implementation.

The distinction concerns the kind of guarantee:

  • Perfect secrecy: ciphertext distributions are exactly identical for every message.
  • Statistical secrecy: the distributions may differ, but only by a small quantified amount, even against an unbounded adversary.
  • Computational secrecy: the distributions need only be indistinguishable to adversaries with bounded computational resources.

The term information-theoretic security encompasses guarantees that do not rely on computational hardness. Perfect secrecy is an exact confidentiality property within that broader category; not every information-theoretic guarantee is perfect secrecy.

Public-key encryption

Ordinary public-key encryption cannot provide perfect secrecy with exact correctness under its standard assumptions.

An unbounded adversary knows the public key and the encryption algorithm. It can enumerate encryption randomness to determine which messages could produce a given ciphertext. For a fixed valid public key, ciphertext supports for distinct messages must be disjoint if decryption always returns the correct message. Identical ciphertext distributions for distinct messages are therefore impossible.

Practical public-key encryption instead relies on computational restrictions. Schemes using additional resources or different correctness and security models must be evaluated under those specific assumptions.

Perfect forward secrecy

Perfect secrecy is distinct from forward secrecy, often called perfect forward secrecy. Forward secrecy concerns whether compromise of long-term keys reveals previously established session keys or past communications.

A protocol can provide forward secrecy while relying entirely on computational assumptions. The word “perfect” in that expression does not imply Shannon’s perfect-secrecy condition.

Scope and limitations

Perfect secrecy is a confidentiality guarantee within a specified threat model. It does not automatically provide other security properties.

No authentication or integrity

The one-time pad is malleable. An adversary can replace CC with C′=C⊕ΔC'=C\oplus\Delta, causing decryption to produce

M′=M⊕Δ.M'=M\oplus\Delta.

This changes selected message bits without requiring knowledge of the key. Perfect secrecy therefore does not imply authentication or protection against message modification. Separate mechanisms and security definitions are needed for those properties.

Length and metadata

The usual one-time-pad proof assumes messages of a fixed length. If ciphertext length reveals plaintext length, the complete observation is not independent of a variable-length message.

Security definitions often permit length leakage by comparing only equal-length messages. Perfect secrecy then applies within the specified length class, not to all possible lengths collectively.

Encryption also does not necessarily conceal metadata such as communication times, participant identities, packet counts, or network routes. Such observations must be included explicitly if the intended guarantee is to cover them.

Auxiliary information and implementation

Perfect secrecy does not conceal information already available from other sources. Where an adversary has auxiliary information ZZ, an appropriate requirement may be

I(M;C∣Z)=0.I(M;C\mid Z)=0.

This states that the ciphertext adds nothing beyond what ZZ already reveals. Its validity depends on how the key, message, and auxiliary information are related. Information exposing the key can invalidate the guarantee.

The mathematical definition also does not by itself address insecure key storage, endpoint compromise, or a side-channel attack. A perfectly secret encryption construction can be deployed in a system that leaks plaintext through mechanisms outside its encryption model.

Historical development and significance

Claude Shannon gave perfect secrecy its foundational mathematical treatment in his 1949 paper Communication Theory of Secrecy Systems. His analysis connected cryptography with probability and information theory, formalizing the idea that intercepted ciphertext should reveal no information about its underlying message.

The one-time pad predates Shannon’s published treatment; his contribution established its secrecy within a general mathematical framework and clarified the key resources required.

Perfect secrecy remains a benchmark for evaluating confidentiality. It precisely separates the absence of information from the practical difficulty of extracting information, and establishes why unrestricted confidentiality against computationally unbounded adversaries requires resources that ordinary reusable-key encryption does not provide.