Just want to make a comment on Zaratustra's solution.

Let's consider a real-world application of the above "cryptography" algorithm. This algorithm only works if our encryption function is commutative, i.e., encrypting with lock A then lock B gives you the same result as encrypting with lock B then lock A. So what encryption algorithms are like that in the real world? The one time pad (maybe others, but let's consider this one for now). The problem with the one time pad is that both parties need a copy of the pad for this simple kind of encryption to work.

But in our example, Alice doesn't need Bob's key, and vice versa, to outsmart Eve. So how come we can't employ their algorithm for use with the one time pad? Well, this is too easy for Eve to break. Let's say Alice has a message M, and generates some random bits A, and sends (A xor M) over to Bob, who has his own random bits B, and sends back (B xor (A xor M)) , which is the same as (A xor (B xor M)). Alice then sends (A xor (A xor (B xor M))), which is the same as (B xor M), since (A xor A) = 0. Bob receives (B xor M), from which he can easily get M.

So what can Eve do? First of all, she sees all the intermediate messages, in particular, (A xor M) and (B xor (A xor M)). She can just xor these two together to get B, then in the last step, when Alice sends over (B xor M), Eve can just use B to get M.

Furthermore, Eve can just generate her own set of bits E, and instead of actually giving the message to Bob in the first step, she just sends back (E xor (A xor M)), and continues the algorithm as if she were Bob. Alice is none the wiser, and in the end Eve is able to get M. This is called a "man in the middle" attack. There are ways around such an attack, though, but that is beyond the scope of this writeup.