SIM security for two messages

Question

Here SIM means the simulation based security

Consider a two message encryption scheme:$$Enc:K \times M \times M \rightarrow C \times C$$

and $Enc(K, m, m')=(K \oplus m, K \oplus m')$, In the real world experiment, the adversary $Eve$ gets $(K \oplus m, K \oplus m')$ as ciphertext, and thus, the information leaked to $Eve$ is $(K\oplus m)\oplus(K \oplus m')=m \oplus m'$, now how should I modify the original ideal world experiment so that in the ideal world, the adversary $Eve$ also gets $m \oplus m'$?

Answer 1

You did not state what the original ideal world experiment is, so we cannot say how it should be modified. In most ideal functionalities for encryption, when Alice encrypts a message for Bob, the ciphertext is not written to the adversary's (simulator's) tape however the length of the message is (and maybe a record of Alice sending something to Bob). In this case, you would modify it so that the simulator would also receive $m \oplus m'$ at the same time.

PS. If you are going to completely change your question (after answers have been posted), you should leave the original question intact and append your new question to the end.

Answer 2

I would highlight Thomas's last point; not only is leaking $m \oplus m'$ failing to provide perfect secrecy, it is often practically insecure.

Exactly how bad this is depends on what those messages actually are (and how they are encoded), but it can be bad indeed. As one example, in my experience, recovering two ASCII English texts from their xor is about as difficult as solving a newspaper cryptogram.

Answer 3

For a given pair of cipher text $(c, c')$, you can compute $x = c \oplus c'$ which is the XOR of the two ciphertexts and is also equal, as you note, to the XOR of the two corresponding plaintexts. Then, for any pair of potential messages $(m, m')$ such that $m \oplus m' = x$, you can compute a corresponding key $K = m \oplus c$; you can verify that $Enc(K, m, m') = (c, c')$. Therefore, the information you have (the ciphertexts $c$ and $c'$) gives you the XOR of the two plaintexts, but since any pair of messages which matches that information is still a possibility, you have no more information than that.

An other way to see it: given a One-Time Pad encryption of a message $m$ with a key $K$ (you know $c = m \oplus K$, but not $m$ or $K$), you can create a random $x$ and compute $c' = c \oplus x$. You then know that $Enc(K, m, m') = (c, c')$ and $m \oplus m' = x$. If you can extract out of that more information than the XOR of $m$ and $m'$ (which the value $x$ you chose), then, congratulations, you have broken One-Time Pad. Given the proven impossibility thereof, one must conclude that out of $(c, c')$ you learn only $m \oplus m'$ and no more.

Mind you, for messages $m$ and $m'$ which are not completely random (e.g. plaintext messages which make sense), the XOR of $m$ and $m'$ is a lot of information; this is the infamous "Two-Times Pad" which has lead to actual decryption in some historical cases (the Wikipedia page on OTP gives a few example, with the Soviet Union in the role of the loser).