# Katz and Lindell, proof of lemma 2.4

Can someone explain the logic behind the claim that the second equality is because we condition on the event that $$M$$ is equal to $$m$$ in the proof of Lemma 2.4 from "Introduction to Modern Cryptography"? I have added the relevant fragment below.

LEMMA 2.4 An encryption scheme (Gen, Enc,Dec) with message space $$\mathcal M$$ is perfectly secret if and only if Equation (2.1) holds for every $$m,m_0 \in M$$ and every $$c \in \mathcal C$$.

PROOF We show that if the stated condition holds, then the scheme is perfectly secret; the converse implication is left to Exercise 2.4. Fix a distribution over $$\mathcal M$$, a message $$m$$, and a ciphertext $$c$$ for which $$\mathrm{Pr}[C = c]$$ > 0.

If $$\mathrm{Pr}[M = m] = 0$$ then we trivially have $$\mathrm{Pr}[M = m | C = c] = 0 = \mathrm{Pr}[M = m].$$ So, assume $$\mathrm{Pr}[M = m] > 0$$. Notice first that $$\mathrm{Pr}[C = c | M = m] = \mathrm{Pr}[\mathrm{Enc}_K(M) = c | M = m] = \mathrm{Pr}[\mathrm{Enc}_K(m) = c],$$ where the first equality is by definition of the random variable $$C$$, and the second is because we condition on the event that $$M$$ is equal to $$m$$.

I'm having a hard time understanding how this follows from (or is connected to) the definition of conditional probability $$\mathrm{Pr}[\mathrm{Enc}_K(M) = c | M = m] = \frac{\mathrm{Pr}[(\mathrm{Enc}_K(M) = c)\wedge(M=m)]}{\mathrm{Pr}[M=m]}.$$

Intuitively, the reasoning behind their statement is that given your random variable $$M$$ equals $$m$$, then $$\mathrm{Enc}_K(M)$$ becomes $$\mathrm{Enc}_K(m)$$.

To see this formally consider the statement $$\mathrm{Pr}[(\mathrm{Enc}_K(M) = c)\wedge(M=m)]$$ from your numerator. Note that $$M$$ refers to the same random experiment on both sides. We may rewrite the statement as $$\mathrm{Pr}[K=k \land M=m : \mathrm{Enc}_k(m) = c]$$ which makes the random choices more explicit. As, by assumption, the choices of random variables $$K$$ and $$M$$ are independent, this equals $$\mathrm{Pr}[K=k: \mathrm{Enc}_k(m) = c]\cdot \mathrm{Pr}[M=m]$$. Writing the first factor more concise again this is just $$\mathrm{Pr}[\mathrm{Enc}_K(m) = c]\cdot \mathrm{Pr}[M=m]$$. Plugging this into your fraction leads, as desired, to $$\mathrm{Pr}[\mathrm{Enc}_K(M) = c | M = m] = \frac{\mathrm{Pr}[(\mathrm{Enc}_K(M) = c)\wedge(M=m)]}{\mathrm{Pr}[M=m]} = \frac{\mathrm{Pr}[(\mathrm{Enc}_K(m) = c)]\cdot \mathrm{Pr}[M=m]}{\mathrm{Pr}[M=m]}=\mathrm{Pr}[\mathrm{Enc}_K(m) = c]$$

After thinking about this for a few days and reviewing basic definitions of random variables and probability distributions (for which I chose Feller's "An Introduction to Probability Theory and Its Applications, Vol. 1"), my conclusion is that the value of the expression $$\mathrm{Pr}[\mathrm{Enc}_K(m) = c]$$ equals the value of the expression $$\mathrm{Pr}[\mathrm{Enc}_K(M) = c | M = m]$$ by definition.

The expression $$\mathrm{Pr}[C = c | M = m]$$ refers to a joint distribution of two random variables $$C$$ and $$M$$, where we can think of the underlying sample space as being formed by pairs $$(m_s,c_s)$$ of messages and ciphertexts. Furthermore, to each sample point $$(m_s,c_s)$$ with probability $$> 0$$ there is at least one key $$k_s \in \mathcal{K}$$ such that $$\mathrm{Enc}_{k_s}(m_s) = c_s$$. Thus, we can in fact think of the sample space as being formed by triples $$(m_s,k_s,c_s)$$. The probability of each triple is given by the distributions of $$\mathcal{K}$$ and $$\mathcal{M}$$.

With this in mind, the first equality $$\mathrm{Pr}[C = c | M = m] = \mathrm{Pr}[\mathrm{Enc}_K(M) = c | M = m]$$ is given by the definition of the random variable $$C$$ and can be seen as replacing $$C$$ with a new random variable $$K$$. The expression $$\mathrm{Pr}[\mathrm{Enc}_K(M) = c | M = m]$$ means the probability that $$K = k$$ given that $$M = m$$, where $$k$$ is instantiated to be the $$k$$ such that $$\mathrm{Enc}_k(M) = c$$. (If there is more than one such $$k$$, then this becomes a bit more complex, having to sum over multiple possible values for $$K$$.)

On the other hand, the expression $$\mathrm{Pr}[\mathrm{Enc}_K(m)=c]$$ means this: restricting ourselves to the sample points where $$M = m$$, what is the probability that $$K = k$$? To compute this value, we would sum the probabilities of the sample points where both $$K = k$$ and $$M = m$$ (presumably there's only one such point) and then divide it by the aggregate of all sample points where $$M=m$$. This is nothing more than the value of $$\mathrm{Pr}[\mathrm{Enc}_K{M}=c|M=m]$$.

Note that the equality $$\mathrm{Pr}[\mathrm{Enc}_K(m)=c] = \mathrm{Pr}[\mathrm{Enc}_K{M}=c|M=m]$$ is true regardless of the assumed independence between $$K$$ and $$M$$. It is a rearrangement of the symbols that makes the choice of random variables more implicit, but their relationship through the $$\mathrm{Enc}$$ function more explicit. For this reason, the answer by @ellipsoid is illuminating but not quite satisfactory to me. By knowing that $$K$$ and $$M$$ are independent, the correct manipulation would be:

\begin{aligned} \mathrm{Pr}[C = c | M = m] &= \mathrm{Pr}[\mathrm{Enc}_K(M) = c | M = m] \\ &= \frac{\mathrm{Pr}[\mathrm{Enc}_K(M) = c \wedge M = m]}{\mathrm{Pr}[M=m]} \\ &= \frac{\mathrm{Pr}[K = k \wedge M = m]}{\mathrm{Pr}[M=m]} \\ &= \frac{\mathrm{Pr}[K = k]\cdot\mathrm{Pr}[M = m]}{\mathrm{Pr}[M=m]} \\ &= \mathrm{Pr}[K = k] \\ &= \mathrm{Pr}[\mathrm{Enc}_K(m) = c]. \end{aligned}

If I get you right (which I'm not sure about), you essentially redefine the random variable $$K$$ which is already defined. Indeed, it is the random variable $$C$$ which is induced by the given $$M$$ and $$K$$. So, you should still think of the sample space as tuples of $$(k,m)$$ and having $$\Pr[C=c]:=\sum_{(k,m): Enc_k(m)=c}\Pr[K=k \land M=m]=\sum_{(k,m): Enc_k(m)=c}\Pr[K=k][M=m]$$ where the last equation holds, since the random variables $$M$$ and (the original) $$K$$ are by assumption (in the book) independent. This also feels more natural to me than... defining $$K$$ by looking on the ciphertexts which may result from the choices of messages and key. As small note, which maybe adds another intuition: If we assume uniformly random choice for $$K$$ and $$M$$ then we'd get $$\Pr[C=c]=|\{(k,m) | Enc_k(m)=c\}|/|\mathcal{K}\cdot\mathcal{M}|$$, since every tuple occurs with the same probability.

If you'd really insist on taking such a route, you would need to a) precisely define your new random variable $$K'$$ and b) then reason/show equality with the given random variable $$K$$. Otherwise your sequence of equations does not relate to the original statement(s) without further arguments.

Finally, your statement that "(for all $$m\in\mathcal{M}$$ and $$c\in\mathcal{C}$$ ) equation $$\mathrm{Pr}[\mathrm{Enc}_K(m)=c] = \mathrm{Pr}[\mathrm{Enc}_K{(M)}=c|M=m]$$ holds regardless of the independence of $$M$$ and $$K$$" is wrong. Note, these statements are $$\mathrm{Pr}[\mathrm{Enc}_K(m)=c]=\sum_{k\in\mathcal{K}: Enc_k(m)=c}\Pr[K=k]$$ $$\mathrm{Pr}[\mathrm{Enc}_K{(M)}=c|M=m]=\sum_{k\in\mathcal{K}: Enc_k(m)=c}\Pr[K=k|M=m]$$

This is not (necessarily) the same for all $$(c,m)$$ when we have no independence (which you can prove using small counterexamples)

Update: Consider for example the following counterexample (and bare with my handwriting) for the single-bit one-time pad where $$Enc_k(m)=c$$ iff $$c=m\oplus k$$. The entries in the table denote the probability of $$\Pr[K=k \land M=m]$$ (which also define the conditional probabilities). Use the (non-independent) probability distribution

There you get following equalities which are certainly not the same

Update 2: As final note, which may helps you with reading such probability statements: Here $$\Pr[Enc_K(m)=c]$$ describes "Probability of $$Enc_k(m)$$ being $$c$$ when sampling $$(k,m')$$ from the (joint) distribution on $$\mathcal{K}\times \mathcal{M}$$ ignoring $$m'$$". $$\Pr[Enc_K(m)=c \land M=m]$$ describes "Probability of $$Enc_k(m)$$ being $$c$$ when sampling $$(k,m)$$ from the (joint) distribution on $$\mathcal{K}\times \mathcal{M}$$".

• The first equation in your comment seems incorrect. Pr[C=c] includes more sample points than those given by (K = k ^ M = m). Also, I would be interested in seeing a counterexample like the one you mention at the end. Apr 6 at 4:38
• 1) The equation holds as for a deterministic encryption algorithm $k$ and $m$ determine $c$, i.e. given $k$ and $m$ there is no randomness used for choosing $c$. As analogue example think of independently rolling two dice (representing their outcome by $K$ and $M$) and computing their sum (represented by $C$). The rolled numbers $k$ and $m$ already determine sum $c=k+m$. The sample space consists of $(k,m)$. You could add $c$ to it, but then for all $(k,m,c)$ with $c\neq k+m$ you'd assign probability 0 (and for the other triples probabiliy $1/36$). 2) I'll sketch a counterexample by time. Apr 7 at 12:25
• I see in the first equation that $k$ and $m$ are variables and not specific $k$ and $m$ as in the proof of Lemma 2.4, so it makes sense to sum over all such $k$ and $m$ to get $Pr[C=c]$.However, think of the cipher in example 2.1, a stream cipher with $\mathcal{M} = {a, b}$ and $\mathcal{K} = {0...25}$, but instead make $K$ depend on the message being encrypted such that $Pr[K=1|M=a] = 1$ and $Pr[K = k|M=b] = 1/26$. In this distribution, $K$ and $M$ are not independent, yet we would still calculate $Pr[\mathrm{Enc}_K(m)=b]$ as $Pr[\mathrm{Enc}_K(m)=b\wedge M=m]/Pr[M=m]$. Apr 7 at 18:13
• No, you don't generally compute it like that: Note that the term $\mathrm{Pr}[\mathrm{Enc}_K(m)=c]$ is well-defined also if we fix some $m$ which occurs with $\Pr[M=m]=0$. The term itself just depends on the result of random variable $K$. Apr 8 at 5:58
• Perhaps this question can be illustrative: how would you calculate $\mathrm{Pr}[\mathrm{Enc}_K(m)=c]$ in a distribution where $\mathcal{K}$ is dependent on $\mathcal{M}$, for example the one in my previous comment? Remembering that all we have is the probability space given by the pairs $(m',k')$. Apr 9 at 5:43