0
$\begingroup$

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$

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – K.G.
    Commented Oct 16, 2016 at 18:54
  • $\begingroup$ 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. $\endgroup$
    – Mohammad Rostami
    Commented Oct 18, 2016 at 9:41
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Commented Oct 19, 2016 at 10:28

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – tylo
    Commented Oct 19, 2016 at 10:50

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.