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.

Dinnage

Is there any serious reason why Alice can't just hold onto K0 and decrypt the token with K0 only after decrypting with the key received from Bob? – Malines

@Lunatic Experimentalist: Yes. This is only a simplified protocol description. What actually happens next is that Alice generates a bunch of keys and encrypts each token herself. Each token is now doubly encrypted. If Bob wants to reveal token X to Alice, he sends his Kx to her. If Alice wants to reveal token X to Bob, she sends her Kx to him. – Dinnage

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

Atonal

I've read a bunch of stuff on mental poker, but all of it assumes a standard 52/54 card deck known to all players. I working with an unknown deck of arbitrary size (unknown in the sense that all available cards are known but the specific ones in the deck are not known to the non-owner). Unfortunately my maths skill is not up to the level that I can adapt what I see about mental poker. Thanks for the reference to SRA - I'll look it up. – Dinnage

Answer 2

below refers to my hobbiest solution using my own cipher program in C#. program and source are free and available.

Remember the 'locked box puzzle' recounted on an SECURITY NOW podcast?

here's the episode... Episode #33 | 30 Mar 2006 | 43 min. Symmetric Block Ciphers

https://www.grc.com/sn/sn-033.txt

Steve says... ...Leo and I answer last week's Puzzler/BrainTeaser which explored the idea of using two private one-time pad "keys," like two padlocks, to securely convey a message between two parties, neither of whom would have the other's key. Then we continue our ongoing tour of fundamental crypto technology by describing the operation of Symmetric Block Ciphers...

Steve and Leo agreed that an eavesdropper seeing ALICE's cipher text before and after encryption could XOR both together and derive her secret key. However, if a complex, commutative cipher which doesn't use simple XORing to encrypt is used then I think the key exchange would be secure and the key exchange would work.

for example... BOB encrypts msg with his key. ALICE encrypts BOB's encrypted above msg with her key. ALICE sends above encrypted msg back to BOB. BOB decrypts ALICE's above msg with his key. BOB sends above to ALICE. ALICE decrypts above with her key. ALICE can now read BOB'S original decrypted cipher text and they didn't need to exchange keys. An eavesdropper attack will not work if the algorithm is not a simple 'xor'ing of plain text and key.

this cipher is a commutative , complex algorithm.

starting with notepad text file containing one character, an 'm'. m is hex 6d 01101101.  is hex c2 11000010 is 'm' encrypted by bob and then sent to alice. ø is hex d8 11011000 is alice's encryption of 'Â' which bob decrypts to '£' and sends to alice. £ is hex a3 10100011 which alice decrypts to 'm' with her key. m is alice decrypt result an eavesdropper sees  alice's msg before her encryption. the eavesdropper sees ø alice's msg after her encryption. the eavesdropper xors  and ø. 11000010 'Â' 11011000 'ø' 00011010 the eavesdropper's xor result = 1a in hex. if an eavesdropper attack worked he would have found 'E' hex 45 01001001 which is first letter of

alice's key.

this seems a simpler key exchange than PGP etc. All that's needed is that both parties use the same crypto program and agree on an authenticator.

I confess to being a hobbiest. If anyone wants the WINDOWS C# .NET program and/or the source code for the cipher they may have it/them.

below is example with longer, random keys.

PLAIN TEXT this is a test.

BOB'S KEY kZtOfS0kKqcRLjTNPh7OjcJKZZFLjmm5OVm02YlrBQN0zI9SxOD1zJjQcpetUbX

BOB'S CIPHER TEXT TO ALICE. 1IÎ.8Ío#"ëìAùJ'

ALICE'S KEY O1yfuV7MpX3n4wtefUhr6YctRaeCcrrzH7LqLNRUQCMVZuL5Mr0Bw3qMeIT92hg

ALICE'S CIPHER TEXT TO BOB µRÖ³#ïÓO,fzkÆaå

BOB DECODES ALICE'S ABOVE WHICH = BELOW. øqqøð<ª>P¸&@<, AND SENDS ABOVE BACK TO ALICE WHICH ALICE DECODES YIELDING... this is a test.

Rebekah

to authenticate simply add agreed upon passwords in plain text inside the message but not part of the message's ciphertext. needed only for last 2 exchanges. e.g., "µRÖ³#ïÓO,fzkÆaå apassword" – Rebekah

Hey! I know its been like, 12 years, but do you still have that c# source code? I'd like to have a look at it. Thanks. – Unicuspid

Answer 3

I'm doing something similar and I'm using AES in OFB (output feedback) mode. In this mode, an IV (publicly known random value) is encrypted with AES using some key. The output of this is then XORed with your data. The output (before being XORed with the data) is then encrypted again to get another output to XOR with more data. This is not only commutative but reciprocal in the sense that the encryption and decryption algorithms are identical. http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Output_Feedback_.28OFB.29

Anaconda

Answer 4

I know the question was asked long ago, but nobody seems to have suggested Massey-Omura, so here it goes. It satisfies the original requirements exactly. The original description (also adopted in Wikipedia) used the multiplicative group of GF(2^m), but any secure group (like elliptic curves) will do.

Lakendra

Thanks. I had become aware of Massey-Omura some time ago (not sure how long after I asked the question), but had not come across an implementation. Searching just now has come up with github.com/apopescu/Massey-Omura. – Dinnage

Answer 5

Here is a page with commutative encryption algorithms :

https://xianmu.github.io/posts/2018-09-19-commutative-encryption.html

Arcane