Consider an encryption scheme $($KeyGen$,$ Enc, Dec$)$ with message space $M,$ key space $K,$ and ciphertext

space $C.$ For any minM, we define a random variable $C(m)$ over $C$ corresponding to the encryption of

$m.$ That is$,C(m)$ is the random variable corresponding to $c$ in the following encryption process:

klarrKeyGen$()$

clarrEnc$(k,m)$

Then, the notion of perfect indistinguishability we saw in the first lecture may be written as follows.

Definition $2\mathrm{.}2($Perfect Indistinguishability $($Probabilities$)).$ The encryption scheme $($KeyGen$,$ Enc, Dec$)$

satisfies perfect indistinguishability if$,$ for any $m_0,m_1$inM and any cinC, we have:

$Pr[C(m_0)=c]=Pr[C(m_1)=c]$

By the observations about advantage earlier, the following is an equivalent definition of perfect

indistinguishability.

Definition $2\mathrm{.}3($Perfect Indistinguishability $($Advantage$)).$ The encryption scheme $($KeyGen$,$ Enc, Dec$)$

satisfies perfect indistinguishability if$,$ for any $m_0,m_1$inM and any algorithm $A,$ we have:

$ad{v}_A^{C(m_0),C(m_1)}=0$

The benefit of writing the definition in terms of the allowed distinguishing advantage is that it gives

us a simple parameter that we can change to weaken the definition. Consider, for instance, the following.

Definition $2\mathrm{.}4(-$Indistinguishability$).$ For $in[0,1],$ the encryption scheme $($KeyGen$,$ Enc, Dec$)$ satisfies

$-$indistinguishability if$,$ for any $m_0,m_1$inM and any algorithm $A,$ we have:

$ad{v}_A^{C(m_0),C(m_1)}$

For very small values of $,$ this is still a meaningful notion of security. One would hope that this

weakening of perfect indistinguishability might allow one to get around Shannon's theorem and use

smaller keys while still being relatively secure$,$ but one would be wrong.

Problem $2\mathrm{.}3(5$ points$).$ Prove that in any encryption scheme that satisfies correctness and $-$indistin$-$

guishability, we necessarily have $|K|(1-)|M|.$

Hint. Try drawing out the mappings like we did while proving Shannon's theorem. Think about how

many elements the supports of $C(m_0)$ and $C(m_1)$ can have in common. How small can you make this

intersection?