# SIM security for two messages

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'$?

-
Looking for a clarification here. You say "In the real world experiment..." and "how should I modify the original ideal world experiment...". I'm not seeing the difference between the "real world experiment" and the "ideal world experiment". What is the difference? – mikeazo Oct 2 '11 at 11:28

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.

-
Actually, the ideal world is defined as following: Ideal world experiment: Repeatedly do: The adversary Eve arbitrarily interacts with the environment. The environment sends a message m to Alice. Alice sends the message m to Bob through a secure channel. – huyichen Oct 3 '11 at 17:19
Eve receives notification that a message was sent through the channel (but does not receive a ciphertext). (Here we assume that the messages come from a finite message space. Otherwise, Eve is notified the length of the message as well.) Eve continues to arbitrarily interact with the environment. The environment outputs a bit (whether Eve caused a particular observable effect on the environment). The adversary is said to "succeed" in the experiment if the environment outputs 1. – huyichen Oct 3 '11 at 17:22
So when Eve receives notification, the notification will include $m \oplus m'$. – PulpSpy Oct 3 '11 at 17:35

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).

-

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.

-