Cryptography - Perfect secrecy $\implies$ adversarial indistinguishability - proof

Question

I'm just starting out with cryptography now and have gone over the various defnitions for a perfectly secret cipher. One of the equvilant definitons is adversarial indistinguishability. When trying to prove the equivilance I had a bit of trouble with one of the directions and ended up finding this proof online:

(Source: http://goutampaul.com/wp-content/uploads/2015/09/lecture4.pdf)

What I don't understand is where they use their inital assumption that the system is perfectly secret. Could someone point it out please?

And am I right to assume that the second C0 in each row at the bottom section is supposed to be C1?

Answer 1

Hopefully I'm able to at least give a partial answer. In the first step of the three equalities, there are three simultaneous steps taken: $$Pr[M=m_0]=Pr[M=m_1]=\frac{1}{2}$$ and $$Pr[b'=b|M=m_0]=Pr[c\in\mathcal{C}_0]$$ and $$Pr[b'=b|M=m_1]=Pr[c\in\mathcal{C}_1].$$ (Yes it seems the second 0's should be 1's). The first one is clear why it's true, as the messages are randomly chosen. The second two however, are not so obvious.

Let's just look at $m = m_0$. What should be clear, is that $b'=b$ if and only if ${\tt Enc}(m_0)\in\mathcal{C}_0$, by the definition of the game and the strategy explained before the equations. So we can say that $$Pr[b'=b|M=m_0]=Pr[{\tt Enc}(m_0)\in\mathcal{C}_0|M=m_0].$$ Writing $c={\tt Enc}(m_0)$, what remains to prove is that $$Pr[c\in\mathcal{C}_0|M=m_0]=Pr[c\in\mathcal{C}_0].$$ Now compare this to Theorem 2.2 of the document you cite, which gives a criterium for perfect secrecy. It is not exactly the same, but it is very similar. This last equality I stated is really a consequence of perfect secrecy, and does definitely not hold in general.

Suppose for example that our encryption scheme gives our ciphertext the same least significant bit as the plaintext, and suppose that $m_0$ has lsb 0 and $m_1$ has lsb 1. Then we can easily choose $\mathcal{C}_0$ and $\mathcal{C}_1$ such that $$Pr[c\in\mathcal{C}_0|M=m_0]=Pr[c\in\mathcal{C}_1|M=m_1]=1.$$ On the other hand, not both $Pr[c\in\mathcal{C}_0]=1$ and $Pr[c\in\mathcal{C}_1]=1$.