Perfectly Secret Encryption

Probability Distribution

Notation

• $\mathcal{K}$ denotes the set of all possible keys (key space)
• $\mathcal{C}$ denotes the set of all possible ciphertexts (ciphertext space)
• $\mathcal{M}$ denotes the set of all possible messages
• $M$ denotes the message, where $M \in \mathcal{M}$
• $K$ denotes the key, where $K \in \mathcal{K}$
• $Gen$ defines a probability distribution for $K$, where $Pr[K=k] = Pr[Gen \space \text{outputs} \space k]$

Assumption

Random variables $M$ and $K$ are independent.

Perfect Secrecy

Definition

An encryption scheme ($Gen$, $Enc$, $Dec$) with message space $\mathcal{M}$ is perfectly secret if for every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$ and every ciphertext $c \in \mathcal{C}$ for which $Pr[\mathcal{C}=c] \gt 0$:

Or

The ciphertext should not leak any additional information about the plaintext regardless of any prior information the attacker has about the plaintext.

Adversarial Indistinguishability Experiment $\text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}$

Let $\Pi = (Gen, Enc, Dec)$ be an encryption scheme with message space $\mathcal{M}$.

Let $\mathcal{A}$ be an adversary.

The experiment $\text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}$ can be defined as follows:

1. $\mathcal{A}$ outputs a pair of messages $m_0, m_1 \in \mathcal{M}$
2. A key $k$ is generated by $Gen$, and a uniform bit $b \in {0,1}$ is chosen. Ciphertext $c \gets Enc_k{(m_b)}$ is given to $\mathcal{A}$. The $c$ is a challenge ciphertext
3. $\mathcal{A}$ outputs a bit $b^\prime$
4. The output of the experiment is defined to be $1$ if $b^\prime = b$, otherwise $0$. $\text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi} = 1$ and $\mathcal{A}$ succeeds, if the output of the experiment is $1$.

The perfect indistinguishability is defined as:

Shanon’s Theorem

Let $(Gen, Enc, Dec)$ be an encryption scheme with message space $\mathcal{M}$, for which $\left| \mathcal{M} \right| = \left| \mathcal{K} \right| = \left| \mathcal{C} \right|$.

The scheme is perfectly secret if and only if:

One-Time Pad (OTP)

Process

• $\mathcal{M} = \{0, 1\}^\ell$
• $Gen$: Choose a uniform key $k \in \{0,1\}^\ell$
• $Enc_k{(m)} = k \oplus m$
• $Dec_k{(c)} = k \oplus c$

Limitation

The key can not be reused. And the key management is difficult.

If the key is reused, a known-plaintext attack will happen:

And the adversary knows $m_1$, then

Or

Which leaks information about $m_1, m_2$, so it is not perfectly secret, the difference between two plaintexts can be identified, and frequency analysis could also be applied.