Perfect Secrecy

Definition

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

$$Pr[M = m | C = c] =Pr[M = m]. \tag{1}$$

(The requirement that $Pr[C = c] > 0$ is a technical one needed to prevent conditioning on a zero probability event.)

This definition implies that in a perfectly secret encryption scheme, the ciphertext $c$ reveals no information about the plaintext $m$. Specifically, for any message $m$ within the message space $\mathcal{M}$ and any possible ciphertext $c$ in the ciphertext space $\mathcal{C}$, the probability of $m$ being the plaintext corresponding to $c$ is exactly the same as the probability of $m$ being chosen without any knowledge of $c$.

Other notions of Perfect Secrecy

There are two other notions of perfect secrecy which are articulated through the following two lemmas:

Lemma 1: An encryption scheme $(Gen, Enc, Dec)$ with message space $\mathcal{M}$ is perfectly secret if and only if the following equation holds for every $m,m' \in \mathcal{M}$ and every $c \in \mathcal{C}$

$$Pr[Enc_K(m) = c] =Pr[Enc_K(m') = c].$$

Proof:

Part 1: $Pr[M = m | C = c] =Pr[M = m] \Longrightarrow Pr[Enc_K(m) = c] =Pr[Enc_K(m') = c].$

According to Bayes' theorem

$$\begin{align*} \underbrace{Pr[M = m | C = c]}_{=Pr[M = m]} \cdot Pr[C = c] &=Pr[C = c | M = m] \cdot Pr[M = m]\\ \implies Pr[C = c] =Pr[C = c | M = m] \tag{A}\\ \implies Pr[C = c] =Pr[C = c | M = m'] \tag{B}\\ \end{align*}$$

Also,

$$\begin{align*} Pr[C = c | M = m ] &= Pr[Enc_K(M) = c|M=m]\hspace{3px}\text{ by definition},\\ &= Pr[Enc_K(m) = c|M=m],\\ &= Pr[Enc_K(m) = c]\hspace{3px}\text{ as K is independent of M}\tag{C}\\ \implies Pr[C = c | M = m'] &= Pr[Enc_K(m') = c]\tag{D} \end{align*}$$

Using (A), (B), (C) and (D), we get

$$\begin{align*} Pr[Enc_K(m) = c] =Pr[Enc_K(m') = c]. \end{align*}$$

Part 2: $Pr[M = m | C = c] =Pr[M = m] \Longleftarrow Pr[Enc_K(m) = c] =Pr[Enc_K(m') = c].$

$$\begin{align*} Pr[Enc_K(m) = c]&=Pr[C = c | M = m ],\\ \text{and } Pr[Enc_K(m') = c]&=Pr[C = c | M = m']\hspace{3px}\text{ by definition}. \end{align*}$$

Because of the premise, we have

$$\begin{align*} Pr[C = c | M = m ]=Pr[C = c | M = m'].\tag{E} \end{align*}$$

We know that

$$\begin{align*} Pr[C = c]&=\sum_{m\in \mathcal{M}}Pr[C = c | M = m]\cdot P[M=m],\\ &=Pr[C = c | M = m_1]\cdot P[M=m_1] + Pr[C = c | M = m_2]\cdot P[M=m_2] +...+Pr[C = c | M = m_{|M|}]\cdot P[M=m_{|M|}],\\ &=Pr[C = c | M = m]\cdot\underbrace{\sum_{m\in \mathcal{M}}P[M=m]}_{=1}\hspace{3px}\text{ using (E)},\\ &=Pr[C = c | M = m]. \tag{F} \end{align*}$$

Using Bayes' theorem

$$\begin{align*} Pr[C = c | M = m]\cdot P[M=m] &= Pr[M = m | C = c]\cdot P[C=c],\\ \implies P[M=m] &= Pr[M = m | C = c]\hspace{3px}\text{ using (F).} \end{align*}$$

$\hspace{480px}\blacksquare$

Lemma 2:

OTP is Perfectly Secret

We will use definition $(1)$ to prove that One Time Pad is perfectly secret.

Given:
$\mathcal{K}=\mathcal{M}=\mathcal{C}=\{0,1\}^l,$ where $l$ is the length of message $m$,

$$\begin{align*} Pr[C = c | M = m] &=Pr[K \oplus m = c | M = m],\\ &= Pr[K = m \oplus c | M = m],\\ &= Pr[K = m \oplus c] \hspace{3px}\text{ as K is independent of M},\\ &=\frac{1}{2^l}. \tag{2} \end{align*}$$ $$\begin{align*} Pr[C = c ] &=\sum_{m \in \mathcal{M} }Pr[C = c | M = m]\cdot Pr[M = m] \hspace{3px}\text{ using law of total probabilty},\\ &= \sum_{m \in \mathcal{M} }\frac{1}{2^l}\cdot Pr[M = m] ,\\ &= \frac{1}{2^l}\cdot \sum_{m \in \mathcal{M} } Pr[M = m] ,\\ &=\frac{1}{2^l}\cdot 1. \tag{3} \end{align*}$$

Now we will use Bayes' theorem of conditional probability:

$$\begin{align*} Pr[C = c | M = m ] &= \frac{Pr[C = c \text{ and } M = m]} {Pr[M = m]},\\ Pr[M = m | C = c ] &= \frac{Pr[C = c \text{ and } M = m]} {Pr[C = c]},\\ \implies Pr[M = m | C = c ] &= \frac{Pr[C = c | M = m ]\cdot Pr[M = m]} {Pr[C = c]},\\ \end{align*}$$

using $(2)$ and $(3)$,

$$\begin{align*} Pr[M = m | C = c ] &= Pr[C = c].\hspace{10px}\blacksquare\\ \end{align*}$$

An inherent limitation exists in crafting an encryption scheme that achieves perfect secrecy, which is encapsulated by the following theorem:

Shannon's Theorem for Perfect Secrecy

Theorem: If $(Gen, Enc, Dec)$ is a perfectly secret encryption scheme with message space $\mathcal{M}$ and key space $\mathcal{K}$, then $|\mathcal{K}|\geq|\mathcal{M}|$.

Proof:

• Assume the contrary: i.e., $|\mathcal{K}| < |\mathcal{M}|$ and the scheme is still perfectly secret
• Fix any message $m_0$, and any key $k_0$. Let

$$c_0=Enc_{k_0}(m_0)\\ \implies Pr[Enc_K(m_0)=c_0]>0$$

• What happens if we decrypt $c_0$ with each key one by one?
  We get a set of messages, which we denote by:

$$S=\{Dec(c_0,k):k \in \mathcal{K}\}$$

• Note that $|S|\leq|\mathcal{K}|$ and $\mathcal{K}<\mathcal{M}$

$$\implies |S|<|\mathcal{M}|$$

• This means, there exists a message $m_1 \in \mathcal{M}$ such that $m_1 \not\in S$
• What happens if we encrypt $m_1$ with a key $k \in \mathcal{K}$?
• Since $m_1 \not\in S$, by definition:

$$\forall k \in \mathcal{k}: Enc_k(m_1)\neq c_0\\ \implies Pr[Enc_K(m_1)=c_0]=0$$

• Therefore, there exist $m_0, m_1, c_0$ such that:

$$Pr[Enc_K(m_o)=c_0] \neq Pr[Enc_K(m_1)=c_0]$$

• This contradicts perfect secrecy.$\hspace{20px}\blacksquare$