Perfect Secrecy

Mort Yao

Definition 1. (Perfect secrecy) An encryption scheme \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\) with message space \(\mathcal{M}\) is said to be perfectly secret if for every probability distribution over \(\mathcal{M}\), every message \(m \in \mathcal{M}\) and every ciphertext \(c \in \mathcal{C}\) (\(\Pr[C=c] > 0\)), it holds that \[\Pr[M=m | C=c] = \Pr[M=m]\]

Definition 2. An encryption scheme \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\) with message space \(\mathcal{M}\) is perfectly secret if for every \(m, m' \in \mathcal{M}\) and every ciphertext \(c \in \mathcal{C}\), \[\Pr[\mathsf{Enc}_K(m) = c] = \Pr[\mathsf{Enc}_K(m') = c]\] where the probabilities are over the choice of \(K\) and the randomness of \(\mathsf{Enc}\).

Lemma 3. Definition 2 is equivalent to Definition 1.

Proof.

i. (\(\Rightarrow\)) Fix a distribution over \(\mathcal{M}\), a message \(m\) and a ciphertext \(c\) for which \(\Pr[C=c] > 0\).

Note that if \(\Pr[M=m] = 0\), we immediately have \[\Pr[M=m | C=c] = 0 = \Pr[M=m]\]

If \(\Pr[M=m] > 0\), there is \[\Pr[C=c | M=m] = \Pr[\mathsf{Enc}_K(M)=c | M=m] = \Pr[\mathsf{Enc}_K(m)=c]\]

Note that given Definition 2, for any \(m' \in \mathcal{M}\), it holds that \(\Pr[\mathsf{Enc}_K(m')=c] = \Pr[C=c | M=m'] = \Pr[\mathsf{Enc}_K(m)=c] = \Pr[C=c | M=m]\). Using Bayes’ Theorem: \[\begin{align*} \Pr[M=m | C=c] &= \frac{\Pr[C=c | M=m] \cdot \Pr[M=m]}{\Pr[C=c]} \\ &= \frac{\Pr[C=c | M=m] \cdot \Pr[M=m]}{\sum_{m' \in \mathcal{M}}\Pr[C=c | M=m'] \cdot \Pr[M=m']} \\ &= \frac{\Pr[M=m]}{\sum_{m' \in \mathcal{M}} \Pr[M=m']} \\ &= \frac{\Pr[M=m]}{1} \\ &= \Pr[M=m] \end{align*}\]

that is, Definition 1 holds if Definition 2 holds.

ii. (\(\Leftarrow\)) Given Definition 1, for every distribution on \(\mathcal{M}\), we have \[\Pr[M=m | C=c] = \Pr[M=m]\]

for all \(m \in \mathcal{M}\) and all \(c \in \mathcal{C}\) for which \(\Pr[C=c] > 0\).

Note that \[\Pr[M=m] = \frac{\Pr[M=m]}{\sum_{m' \in \mathcal{M}} \Pr[M=m']}\]

Also by Bayes’ Theorem: \[\begin{align*} \Pr[M=m | C=c] &= \frac{\Pr[C=c | M=m] \cdot \Pr[M=m]}{\Pr[C=c]} \\ &= \frac{\Pr[C=c | M=m] \cdot \Pr[M=m]}{\sum_{m' \in \mathcal{M}}\Pr[C=c | M=m'] \cdot \Pr[M=m']} \end{align*}\]

For the equation in Definition 1 to hold, it must hold true that \[\Pr[C=c | M=m] = \Pr[C=c | M=m']\]

for any value of \(m'\), and \(\Pr[M=m] \neq 0\).

Therefore, \[\begin{align*} \Pr[\mathsf{Enc}_K(m)=c] = \Pr[C=c | M=m] &= \Pr[C=c | M=m'] \\ &= \Pr[\mathsf{Enc}_K(m')=c] \end{align*}\]

that is, Definition 2 holds if Definition 1 holds.

■

Adversarial indistinguishability experiment \(\mathsf{PrivK}_{\mathcal{A},\Pi}^\mathsf{eav}\):

  1. The adversary \(\mathcal{A}\) outputs a pair of messages \(m_0, m_1 \in \mathcal{M}\).
  2. A key \(k\) is generated using \(\mathsf{Gen}\) and a uniformly random bit \(b \in \{0,1\}\) is chosen; both are unknown to \(\mathcal{A}\). A ciphertext \(c \leftarrow \mathsf{Enc}_k(m_b)\) (called the challenge ciphertext) is computed and given to \(\mathcal{A}\).
  3. \(\mathcal{A}\) outputs a bit \(b'\).
  4. If \(b'=b\), the output of the experiment is defined to be \(\mathsf{PrivK}_{\mathcal{A},\Pi}^\mathsf{eav} = 1\) (\(\mathcal{A}\) succeeds in the game); otherwise, it is defined to be 0 (\(\mathcal{A}\) fails in the game).

Definition 4. (Perfect indistinguishability) An encryption scheme \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\) with message space \(\mathcal{M}\) is said to be perfectly indistinguishable if for every \(\mathcal{A}\), it holds that \[\Pr\left[ \mathsf{PrivK}_{\mathcal{A},\Pi}^\mathsf{eav} = 1 \right] = \frac{1}{2}\]

Clearly, any adversary can succeed in the game with probability \(\frac{1}{2}\) by making a random guess on the unknown bit \(b\). Intuitively, the definition of perfect indistinguishability says that no adversary can do better than this.

Lemma 5. Definition 3 (perfect indistinguishability) is equivalent to Definition 1 (perfect secrecy).

Theorem 6. By redefining the key space, we can assume that any encryption scheme \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\) with message space \(\mathcal{M}\) satisfies

  1. \(\mathsf{Gen}\) chooses a key uniformly at random from the key space.
  2. \(\mathsf{Enc}\) is deterministic.

without changing \(\Pr[C=c | M=m]\) for any \(m,c\).

Theorem 7. If \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\) is a perfectly secret encryption scheme with message space \(\mathcal{M}\) and key space \(\mathcal{K}\), then it must hold that \[|\mathcal{K}| \geq |\mathcal{M}|\]

Theorem 7 shows an important inherent limitation of perfect secrecy: For any encryption scheme to be perfectly secret (“theoretically unbreakable”), it must have a key space which is no smaller than the message space. In other words, assume that both the key and the message are encoded as binary strings, the key should be a uniform binary string which is (at least) as long as the message to be encrypted.

Theorem 8. (Shannon’s theorem) Let \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\) be an encryption scheme with message space \(\mathcal{M}\) and key space \(\mathcal{K}\), for which \(|\mathcal{M}| = |\mathcal{K}| = |\mathcal{C}|\). The scheme is perfectly secret if and only if:

  1. Every \(k \in \mathcal{K}\) is chosen by \(\mathsf{Gen}\) with the same probability \(\frac{1}{|\mathcal{K}|}\).
  2. For every \(m \in \mathcal{M}\) and every \(c \in \mathcal{C}\), there exists a unique key \(k \in \mathcal{K}\) such that \(\mathsf{Enc}_k(m)\) outputs \(c\).

Practical construction. A practical construction of perfectly secret encryption schemes is called the one-time pad (OTP). It is easy to verify that the two conditions specified in Shannon’s theorem are satisfied by the one-time pad.