Proving two definitions of perfect security are equivalent

Question

I'm trying to prove that the following two definitions are equivalent:

$\forall m\in M $ and $c\in C$ $\Pr[C=c \mid M=m]=\Pr[C=c]$

$\forall m_1,m_2 \in M $, $E_k(m_1)=E_k(m_2)$, where $E_k(m_i)$ stands for the distribution over $k$ of the encrypted message $m_i$.

First - just to make sure, I am indeed supposed to show two directions, right? (i.e. first $\Rightarrow$ second and second $\Rightarrow$ first). This is my understanding regarding showing an equivalence for any two definitions.

If so, I'm able to prove the direction first $\Rightarrow$ second but I'm unable to do the second direction. How do I use the fact that for every pair of messages I have some conclusion about any single general message $m$?

Thanks.

Answer 1

Yes, you are right, you need to prove both directions. In Katz & Lindell's textbook (2nd edition) you can find the proof for first $\Rightarrow$ second. The other direction is left for exercise. I try my best to give a correct solution for that.

First we have to know that the following holds:

$$ Pr[Enc_k(m) = c] = Pr[C = c | M = m] $$

First $\Rightarrow$ Second proves, that assuming $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ is correct, then $Pr[C = c | M = m] = Pr[M = m]$ holds.

We want to show that assuming $Pr[C = c | M = m] = Pr[M = m]$ is correct, then $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ holds.

My solution is:

$$Pr[Enc_k(m_1) = c] = Pr[C = c | M = m_1] = \frac{Pr[M = m_1 | C = c] \cdot Pr[C = c]}{Pr[M=m_1]} $$

Because we assumed that $Pr [ M = m_1 | C = c] = Pr[M=m_1]$ we get:

$$ \Rightarrow Pr[C = c] = Pr[C = c | M = m_2] = Pr[Enc_k(m_2) = c]$$