# 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]}.$$

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. Commented 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. Commented 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]$. Commented 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$. Commented 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')$. Commented Apr 9 at 5:43

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]$$