# Is there an encryption scheme that provides $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\}$

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$

• Consider the case where $c_1 \not= c_2$. What is the probability that $m_1 \not= m_2$? (The computation is more complicated if you allow randomized encryption, so assume deterministic encryption first.) PS. The claim is only true if you consider stateless encryption.
– K.G.
Commented Oct 16, 2016 at 18:54
• I know that there is a system satisfying this definition of perfect secrecy, if $c_1\neq c_2$ and $m_1\neq m_2$ but I am trying to prove that there is no encryption scheme that provides $^{(*)}$ in the question. Commented Oct 18, 2016 at 9:41
• The question is actually missing the definitions of $Gen,Enc,Dec$, and how your $m_i$ and $c_i$ are related. Even if $c_i = Enc(m_i)$ is fairly obvious, it has to be stated explicitly if you're doing a formal proof. And then the repeating statements $C_1 = c_1 \wedge C_2 = c_2$ in every probability (and the same for all $m_i$) is probably unnecessarily complicated.
– tylo
Commented Oct 19, 2016 at 10:28

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 $^{(*)}$

• You are on the right track, but your arguments are not correctly stated. The case of $m_1 \neq m2, c_1 = _2$ is in contradiction to an encryption scheme, but you didn't state why (encryption has to be injective, otherwise decryption is not unique). The Probability starting with $Pr\{k\leftarrow Gen();c=...$ does not make sense, and $\hat{m}$ isn't defined at all. I would suggest going a different route: Use proper definitions of the algorithms, and then assume two cases: $c_1 = c_2$ and $c_1 = c_2$, and then show that the distributions are not equal. Don't try to force a proof by contradiction
– tylo
Commented Oct 19, 2016 at 10:50