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:

enter image description here

(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?


1 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$.


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.