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

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

CC BY-SA 3.0
2012-12-02T20:02:05.030Z
2012-12-02T20:02:05.030Z
user6584
<p>My initial crack at a solution is the following, please let me know what you think</p>

<p>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) &gt; 0$ and $p_{\mathcal{M}}(m_1) &gt; 0$. </p>

<p>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\} $.</p>

<p>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>

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

<p>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}$. </p>

<p><strong>Claim 1</strong>: 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.</p>

<p><strong>Claim 2</strong>: 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) &amp;= p(C=c \mid M=m_0)p(M=m_0) \\
&amp;= p'(C = c \mid M = m_0)p(M = m_0), \text{ by the above discussion} \\
&amp;= p'(C=c)p(M= m_0), \text{ since (Gen, Enc, Dec) is perfectly secret
  for } p'_{\mathcal{M}} \\
&amp;= p'(C=c) \sum_{m \in N'} p'(M = m) \\
&amp;= p'(C=c) \sum_{m \in N'} p'(M = m \mid C = c) \\
&amp;= \sum_{m \in N'} p'(M=m, C=c)
\end{align*}
$$</p>

<p>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 </p>

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

<p>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)$$
. </p>

<p>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) &amp;= \frac{p(M=m_0, C=c)}{p(C=c)} \\
&amp;= \sum_{m \in N'} \frac{p'(M=m, C=c)}{p'(C=c)}, \text{ by Claim 2} \\
&amp;= \sum_{m \in N'} p'(M=m \mid C=c) \\ 
&amp;= \sum_{m \in N'} p'(M=m), \text{ since (Gen, Enc, Dec) is
  perfectly secret w.r.t }p'_{\mathcal{M}}\\ 
&amp;= p(M=m_0), \text{ by definition of }p'_{\mathcal{M}}
\end{align}
$$
And so the claim is proven.</p>

CC BY-SA 3.0
2012-05-17T02:56:22.673Z
2017-08-27T16:03:55.530Z
2017-08-27T16:03:55.530Z
drewbarbs
<p>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:</p>

<blockquote>
  <p>Say encryption scheme (Gen,Enc,Dec) satisﬁes Deﬁnition 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 satisﬁes 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}&#39; \subset \mathcal{M}$</p>
</blockquote>

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

<blockquote>
  <p>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] &gt; 0$ :<br>
  $\Pr[M = m \mid C = c] = Pr[M = m]$</p>
</blockquote>

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

<cr.crypto-security>
Justifying simplifying assumption about message distributions for perfectly secret encryption?
drewbarbs
# Justifying simplifying assumption about message distributions for perfectly secret encryption?

(Asked by: username_0 on 2012-05-16)

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) satisﬁes Deﬁnition 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 satisﬁes 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?

**Tags:** cr.crypto-security

---

## 2 answers

### Answer by username_1 on 2012-12-02. Score: 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 by username_0 on 2012-05-17. Score: 1

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.


---

