Perfect Secrecy

cryptography

Definition

Perfect Secrecy

An encryption scheme provides perfect secrecy if observing the ciphertext does not reveal any information about the corresponding plaintext.

Formally, let $M$, $C$, $K$ be random variables denoting plaintext, ciphertext, and key, with $K$ uniformly distributed and independent of $M$. The scheme provides perfect secrecy if for every probability distribution over the message space, every message $m\in \mathcal{M}$, and every ciphertext $c\in \mathcal{C}$,

$$\mathrm{Pr}[M=m\mid C=c]=\mathrm{Pr}[M=m]$$

This means that the information of the ciphertext provides me with no additional information the actual plaintext.

Key Requirement

Key Space Size

Let $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be a cipher providing perfect secrecy with $\mathrm{Pr}[C=c]>0$ for every ciphertext $c$. Then the key space size is at least the message space size:

$$|\mathcal{K}|\ge |\mathcal{M}|$$

Example

One-Time-Pad

The One-Time-Pad is the first cipher proved to offer perfect secrecy (Shannon, 1949). The plaintext, ciphertext, and key are bitstrings of equal length; the key is randomly generated and used exactly once.