Perfect Security

Updated 03 Sep 2026

•
Definition
- •
  a Shannon Cipher $\mathcal{E}$ is perfectly secure if for all messages $m_0, m_1$ and all ciphertexts $c$ : $\Pr[E(k, m_0) = c] = \Pr[E(k, m_1) = c]$ , where $k$ is uniform over the key space
- •
  intuitively: seeing the ciphertext gives an adversary zero information about which message was sent
•
Equivalent characterizations
- •
  for every ciphertext $c$ , the number of keys mapping any given message to $c$ is the same, regardless of which message
- •
  for every predicate $\phi$ on ciphertexts (however clever), $\Pr[\phi(E(k,m_0))] = \Pr[\phi(E(k,m_1))]$ — no test can distinguish encryptions of different messages
- •
  the ciphertext $c$ and the message $m$ are independent random variables (assuming $k$ and $m$ are chosen independently)
•
The "gold standard"
- •
  the strongest possible notion of secrecy for a single-message cipher — but see Shannon's Theorem for why it's impractical
•
Related

Linked references 6