3
$\begingroup$

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

$\endgroup$

2 Answers 2

0
$\begingroup$

I add this as another answer, as the lack of reputation prevents me from commenting your own answer @MuchToLearn. An edit of my original answer may would be overseen. Additionally this answer may add something to the initial question and probably resolves some misunderstandings.

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 probability distribution with dependencies

There you get following equalities which are certainly not the same enter image description here

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}$".

$\endgroup$
19
  • $\begingroup$ 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. $\endgroup$ Commented Apr 6 at 4:38
  • $\begingroup$ 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. $\endgroup$
    – ellipsoid
    Commented Apr 7 at 12:25
  • $\begingroup$ 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]$. $\endgroup$ Commented Apr 7 at 18:13
  • $\begingroup$ 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$. $\endgroup$
    – ellipsoid
    Commented Apr 8 at 5:58
  • $\begingroup$ 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')$. $\endgroup$ Commented Apr 9 at 5:43
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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