Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 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.

share|improve this answer

(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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.