A commutative cipher?

Question

I am looking for a commutative cipher - that is

E(K₁,E(K₂,P)) = E(K₂,E(K₁,P))

but is not associative - that is

E(K,P) ≠ E(P,K)

That rules out XOR, which otherwise would have been ok.

A symmetric cipher would be preferable, but an asymmetric cipher would work too.

The basic protocol I want to implement is:

1. Alice has a list of tokens (32-bit integers) and she encrypts each token with the same key (K0)
2. Alice sends the list of encrypted tokens to Bob
3. Bob randomises the list, encrypts each token with a separate key (K1 - Kn), labels each token and returns the list to Alice.
4. Alice decrypts each token with K0, leaving her a list of tokens, each encrypted with a separate key (K1 - Kn)
5. Sometime later, Bob sends Alice a key for a specific label (Kx)
6. Alice decrypts the token with Kx giving her the plaintext for the token labelled x
7. Bob may see the plaintext, so he must not be able to derive K0 from it given the information he was previously given.

Can someone suggest a cipher I can use and also point me to an implementation of that cipher?

I have an understanding of cryptographic protocols and applications but I don't really grok the mathematics of most of the ciphers out there. Step-by-step mathematical guides would be ok though.

I plan to implement this in Clojure so any Java libraries are also good. However, any code is good because I understand code.

Answer 1

It sounds like you're trying to implement "Mental Poker" (or if not, you should look up the research into it, since it's analagous to your problem).

The SRA algorithm has the properties you desire. It's a bit hard to find information on, but it is essentially just RSA except that both the e and d exponents are kept secret. Trivially:

(P^e1)^e2 == (P^e2)^e1