Justifying simplifying assumption about message distributions for perfectly secret encryption?

Question

I am currently reviewing my way through Katz and Lindell's Intro to Modern Cryptography, and have found the following question early in the book (exercise 2.6) surprisingly difficult to answer cleanly:

Say encryption scheme (Gen,Enc,Dec) satisfies Definition 2.1 for all distributions over $\mathcal{M}$ that assign non-zero probability to each $m\in \mathcal{M}$ (as per the simplifying convention used in this chapter). Show that the scheme satisfies the definition for all distributions over $\mathcal{M}$ (i.e. including those that assign zero probability to some messages in $\mathcal{M}$). Conclude that the scheme is also perfectly secret for any message space $\mathcal{M}' \subset \mathcal{M}$

Where $\mathcal{M}$ is the message space the encryption scheme is defined over, and def 2.1 is

An encryption scheme (Gen,Enc,Dec) over a 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[C = c] > 0$ :
$\Pr[M = m \mid C = c] = Pr[M = m]$

Maybe I am just missing something really basic, does anyone have a simple solution?

Answer 1

(1) You should try emailing the authors directly (their address is in the forward) --- they are quite responsive to people asking questions about their book.

(2) Here is a sketch of another solution. First, observe that perfect secrecy for all distributions that assign non-zero probability to each $m$ implies that for any $m, m' \in {\cal M}$ and any ciphertext $c$ we have $\Pr[{\sf Enc}_K(m)=c] = \Pr[{\sf Enc}_K(m')=c]$ (the probability is over choice of key $k$). This, in turn, implies that to each $c$ we can assign a number $\delta_c$ such that $\Pr[{\sf Enc}_K(m)=c]$ for any $m \in {\cal M}$. From there, you can now work directly with the definition of perfect secrecy to show that perfect secrecy holds even for distributions that assign 0 probability to some messages.

Answer 2

My initial crack at a solution is the following, please let me know what you think

Fix an encryption scheme (Gen, Enc, Dec) satisfying definiton 2.1 for all distributions over $\mathcal{M}$ that assign non-zero probability to each $m\in \mathcal{M}$. Fix a distribution $p_{\mathcal{M}}$ over $\mathcal{M}$ for which $\exists m \in \mathcal{M}$ such that $p_{\mathcal{M}}(m) = 0$. Let $N$ denote the set of all such $m$. To avoid triviality, assume $\exists$ at least 2 messages $m_0, m_1 \in \mathcal{M}$ such that $p_{\mathcal{M}}(m_0) > 0$ and $p_{\mathcal{M}}(m_1) > 0$.

Now, we let $p^* = p_{\mathcal{M}}(m_0)$, and create an "altered" distribution as follows. Let $p'_{\mathcal{M}}(m) = p_{\mathcal{M}}(m)$ for all $m \in \mathcal{M} \setminus (N \cup \{m_0\})$, and let $p'_{\mathcal{M}}(m) = \frac{p(m_0)}{| N \; \cup \; \{m_0\} |}$ (that is, the altered distribution is the same as the original, except it distributes the probability $p_{\mathcal{M}}(m_0)$ evenly amongst $m_0$ and all the messages in $N$). For notational convenience, let $N' := N \; \cup \; \{m_0\} $.

Now, $p'_{\mathcal{M}}$ is a distribution in which all messages have non-zero probability, so (Gen, Enc, Dec) is perfectly secret with respect to this distribution. That is, Gen and Enc define a distribution over the set of ciphertexts $\mathcal{C}$ such that:

$$p'(M = m \mid C = c) = \frac{p'(M=m, C = c)}{p'(C = c)} = p'(M = m)$$

for all $m \in \mathcal{M}, c \in \mathcal{C}$. (Here $p'$ denotes the joint probability over messages and ciphertexts determined by the distribution $p'_{\mathcal{M}}$ over $\mathcal{M}$, the distribution over keys generated by Gen, and the randomness of Enc). Then, I claim, (Gen, Enc, Dec) must be perfectly secret with respect to the original distribution, $p_{\mathcal{M}}$ over $\mathcal{M}$.

Claim 1: For all $m \not \in N'$, and for all $c \in \mathcal{C}$: $$p'(M=m, C=c) = p(M=m, C=c)$$ (where $p'$ is as before and $p$ denotes the joint probability over messages and ciphertexts determined by the distribution $p_{\mathcal{M}}$ over $\mathcal{M}$, the distribution over keys generated by Gen, and the randomness of Enc). The reason this holds is that Gen and Enc act independently of the distribution over $\mathcal{M}$. Since $p'_{\mathcal{M}}(m) = p_{\mathcal{M}}(m) \forall m \not \in N'$, the claim follows.

Claim 2: For all $c \in \mathcal{C}$: $$p(M=m_0, C=c) = \sum_{m \in N'} p'(M=m, C=c) $$ First, we note that for any $c\in \mathcal{C}$ and for any $m \in \mathcal{M} \setminus N'$, $p(C=c \mid M= m) = p'(C = c \mid M = m)$, since the randomness of Gen and Enc are completely independent of the distribution over $\mathcal{M}$, and so the message-conditional probability of any particular ciphertext is equal. Then, fix $c\in \mathcal{C}$ $$ \begin{align*} p(M=m_0, C = c) &= p(C=c \mid M=m_0)p(M=m_0) \\ &= p'(C = c \mid M = m_0)p(M = m_0), \text{ by the above discussion} \\ &= p'(C=c)p(M= m_0), \text{ since (Gen, Enc, Dec) is perfectly secret for } p'_{\mathcal{M}} \\ &= p'(C=c) \sum_{m \in N'} p'(M = m) \\ &= p'(C=c) \sum_{m \in N'} p'(M = m \mid C = c) \\ &= \sum_{m \in N'} p'(M=m, C=c) \end{align*} $$

Thus, since $$p(C = c) = \sum_{m \in \mathcal{M}} p(M=m, C=c) = \sum_{m \in \mathcal{M}} p'(M=m, C=c) = p'(C=c)$$ we see that the distribution over ciphertexts remains the same with respect to both distributions over $\mathcal{M}$. Combined with Claim 1, we see that

$$ \begin{align} p(M =m \mid C=c) &= \frac{p(M=m, C=c)}{p(C=c)} \\ &= \frac{p'(M=m, C=c)}{p'(C=c)} \\ &= p'(M=m \mid C=c) \\ &= p'(M=m) \\ &= p(M=m) \end{align} $$

for all $m \in \mathcal{M} \setminus N'$ and all $c \in \mathcal{C}$. For $m \in N' \setminus \{m_0\}$, $$p(M= m \mid C = c) = 0 = p(M=m)$$ .

What remains to be seen is that $p(M=m_0 \mid C = c) = p(M =m_0)$. This is the case, since for all $c \in \mathcal{C}$ $$ \begin{align} p(M=m_0 \mid C = c) &= \frac{p(M=m_0, C=c)}{p(C=c)} \\ &= \sum_{m \in N'} \frac{p'(M=m, C=c)}{p'(C=c)}, \text{ by Claim 2} \\ &= \sum_{m \in N'} p'(M=m \mid C=c) \\ &= \sum_{m \in N'} p'(M=m), \text{ since (Gen, Enc, Dec) is perfectly secret w.r.t }p'_{\mathcal{M}}\\ &= p(M=m_0), \text{ by definition of }p'_{\mathcal{M}} \end{align} $$ And so the claim is proven.