1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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