# Please prove distinguishability given a non-perfectly secure cipher

I'm trying to prove that a perfectly secure cipher yields indistinguishability. I already know and can prove that a perfect cipher => indistinguishability by the following proof:

\begin{align} \Pr(Enc(m_1) = c) = & \Pr(C = c | P = m_1) \\ & = \frac{\Pr(C = c \land P = m_1)}{\Pr(P = m_1)} \\ & = \frac{\Pr(C = c) | \Pr(P = m_1|C = c)}{\Pr(P = m_1)}\\ & = \frac{\Pr(C = c) | \Pr(P = m_1)}{\Pr(P = m_1)}\\ & = \Pr(C = c)\\ \end{align}

Please help me prove indistinguishability will yield a perfect/secure cipher (indistinguishability => perfect cipher) which is the opposite direction.

The proof in the question is not about the perfect secrecy $$\implies$$ indistinguishability. It is about proving that; if perfect secrecy than we have $$Pr[C=c| M=m] = Pr[C=c]$$ Also, we don't need the $$\wedge$$ step, just use Bayes' Theorem directly. The reverse (1) of this also true that is if we have $$Pr[C=c| M=m] = Pr[C=c]$$ that we have perfect secrecy.

Now assuming that we have indistinguishability. That is; for every probability distribution over the message space $$\mathcal{M}$$ and every $$m_0,m_1 \in \mathcal{M}$$, and for every $$c \in \mathcal{C}$$;

$$Pr[C=c| M=m_0] = Pr[C=c | M=m_1]$$ we will show that we have prefect secrecy.

Since, the equation holds for ever $$m_0,m_1$$ we can say $$Pr[C=c| M=m_0] = Pr[C=c | M=m_1] = p$$ (2).

Now, write $$Pr[C=c]$$ as;

\begin{align} Pr[C=c] & = \sum_{m\in\mathcal{M}} Pr[C=c | M=m] \cdot Pr[M=m] \\ & = \sum_{m\in\mathcal{M}} p \cdot Pr[M=m] \\ & = p \sum_{m\in\mathcal{M}} Pr[M=m] \quad\quad\quad\quad \\ & = p \\ & = Pr[C=c| M = m_0] \quad\quad\quad\quad\quad\quad//(\text{use }2) \end{align} we have;

$$Pr[C=c] = Pr[C=c| M = m_0]$$ ,

now use (2);

$$Pr[M=m | C=c] = Pr[M = m_0]$$ therefore, indistinguishability $$\implies$$ perfect cipher