Question:
Consider the following definition of perfect secrecy for the encryption of two messages.An encryption scheme (Gen, Enc, Dec) over a message space M is perfectly-secret fortwo messages if for all distributions over M, and for all $m_1,m_2 \in M$ an d $c_1, c_2 \in C$ with $Pr\{C_1 =~c_1 \wedge C_2 =~c_2\} > 0$:
$^{(*)}$$Pr\{M_1 = m_1\wedge M_2 = m_2 | C_1 = c_1 \wedge C_2 = c_2\} = Pr\{M_1 = m_1 \wedge M_2 = m_2\}$, where $m_1$ and $m_2$ are sampled independently from the same distribution over M. Prove that no encryption scheme satisfies this definition.
My induction:
So I think if an encryption scheme provides $^{(*)}$ then it can't provide the corectness condition.
($Pr\{k\longleftarrow Gen();c=Enc_k(m);\hat{m}=Dec_k(c):m=\hat{m}\}=1$)
because let $m_1,m_2=m$ and $c_1,c_2=Dec_k(m)$ in $^{(*)}$. it's seems that we can't determine if $c$ is the cipher of $m$ or not but I can't also prove that
$Pr\{k\longleftarrow Gen();c=Enc_k(m);\hat{m}=Dec_k(c):m=\hat{m}\}<1$
let $M_1,M_2$ be a distribution where $\exists m_1,m_2$ that $ Pr\{M_1=~m_1 \wedge~M_2=~m_2\} \neq 0$ and $m_1 \neq m_2$ it is clear that such distribution exist.
suppose $\Pi$(Gen,Enc,Dec) satisfy the question's statement and $|M|\neq 1$
Let $m_1\neq m_2$ but $c_1=c_2=c$
$^{(*)}$ $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}=Pr\{M_1=~m_1 \wedge~M_2=~m_2\} $
if $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}\neq 0$ then $m_1,m_2$ are encrypted with the same key the above probability is not equal to 0 so
$Pr\{k\leftarrow Gen();c=Enc_k(m);\hat{m}=Dec_k(c):m=\hat{m}\} \neq 1$ but this is in paradox with $\Pi$ being a encryption scheme.
so $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}= 0$ and according to $^{(*)}$ $ Pr\{M_1=~m_1 \wedge~M_2=~m_2\} $ is also equal to zero $\forall m_1 \neq m_2$ which is also in paradox with the way we chose our distributions.
So no encryption scheme could satisfy $^{(*)}$