Perfect Secrecy for two distinct messages

Question

We say that and encryption scheme $\pi$ is perfectly secret for two distinct messages, if for all distributions over $\mathcal{M}\times\mathcal{M}$ ($\mathcal{M}$ is the message space), for all $m_1,m_2\in\mathcal{M}$ such that $ m_1\ne m_2$ and all $c_1,c_2\in\mathcal{C}$ (where $\mathcal{C}$ is the cypher text space) such that $\text{Pr}[C_1=c_1\wedge C_2=c_2]>0$ then $$\text{Pr}[M_1=m_1\wedge M_2=m_2|C_1=c_1\wedge C_2=c_2]=\text{Pr}[M_1=m_1\wedge M_2=m_2]$$

I am trying to come up with an encryption scheme that satisfies this definition. So far this is what I have come up with

Say $\mathcal{M}=\{0,1\}^l, \mathcal{K}=\{(0,1),(1,0),(0,0),(1,1)\}^l, \mathcal{C}=\{0,1\}^l$

$k\leftarrow\text{Gen}(\mathcal{K})$

Now let $m_i$ denote the $i^{th}$ bit of $m$.

Let $c_i$ denote the $i^{th}$ bit of $c$.

And let $k_{il}$ denote the $l$ bit of the $i^{th}$ pair in $k$ and (l=0 for the first, l=1 for the second)

$\text{Enc}_k(m):$ For all $m_i$ in $m$ (iterating through bits)

if $m_i=0$: $ c_i=m_i \oplus k_{i0}$

else: $c_i=m_i \oplus k_{i1}$

Return $c$

$\text{Dec}_k(c)$: For all $c_i$ in $c$ (iterating through the bits of $c$)

if $c_i=1$: $m_i=m_i \oplus k_{i0}$

else: $m_i=c_i \oplus k_{i1}$

Return $m$

Does this work? I feel like it should because essentially what we've done is essentially create a key that can perform a one-time pad twice safely

Answer 1

Let $m_i := 0$ and $k_i := \langle 0, 1 \rangle$. Then $c_i = Enc_{k_i}(m_i) = m_i \oplus k_{i0} = 0\ \oplus\ 0 = 0$. But then $m'_i = Dec_{k_i}(c_i) = c_i \oplus k_{i1} = 0\ \oplus\ 1 = 1$, and we have $m_i \neq m'_i$. The same holds for $m_i := 1$ and $k_i := \langle 1, 0 \rangle$. So your encryption scheme might give perfect secrecy, but it does not allow you to decrypt the message.

This is because your encryption scheme effectively loses information from the message when encrypting with a key of $k_i = \langle 0, 1 \rangle$ or $k_i = \langle 1, 0 \rangle$, and for these keys the ciphertext $c_i$ is solely determined by the key:

$Enc_{\langle 0, 1 \rangle}(0) = 0\ \oplus\ 0 = 0\\ Enc_{\langle 0, 1 \rangle}(1) = 1\ \oplus\ 1 = 0\\ Enc_{\langle 1, 0 \rangle}(0) = 0\ \oplus\ 1 = 1\\ Enc_{\langle 1, 0 \rangle}(1) = 1\ \oplus\ 0 = 1$

If you reduce the keyspace to $\mathcal{K} = \{\langle 0, 0 \rangle, \langle 1, 1 \rangle\}^l$ you effectively have a regular one-time pad.

Answer 2

Basically, if your key $k$ is the same size as the two messages combined, and if each bit of the two messages is encrypted completely independent of each other (with XOR) then you have a one-time-pad. I guess you can easily proof that the (first) value of $k_{xy}$ is independent of $y$. In that case you seem to have a one-time-pad.

Your scheme presumes two messages of the same size, it seems. That's OK, but it is something worth noting.