Software implementation of a commutative cipher? I've got an application (detailed below) that calls for the use of a cipher that is commutative.  I've been doing some googling &amp; reading, and there are two algorithms that seem to get mentioned in these discussions--SRA (not RSA) and Pohlig-Hellman exponentiation.  (Supposedly SRA is a variant of RSA?).  I need something strong, so XOR will not serve.

I'd hoped to run across some actual software that implemented one of these guys so I could play around with them &amp; demonstrate a scheme I have in mind, but I have not been able to find any.  It looks to me like these things are not in the source code that comes with Schneier's Applied Cryptography, frx. Can anyone recommend a source for implementations of either SRA or Pohlig-Hellman?



Here's how I'm thinking to use this tech if I can get my hands on it.  I work for a healthcare provider A, which operates in the same geographic area as our colleague/competitor provider B.  We know that we share some patients, but we don't know which, or even how many people we have in common.

We could just swap lists of say, the SSNs of our patients &amp; find out who we share, except that we don't really trust each other to treat this sensitive data w/the care that it's due, and wow would people freak out and hate us if it got out that we were making free w/their SSNs, etc. etc..  So--please take for granted that sending raw SSNs is neither practical nor desirable.

But here's what we maybe can do.  I grab my commutative-cipher software, generate an encryption key, save it off somewhere safe, and produce a file of encrypted SSNs (each SSN encrypted separately with my key).  My colleague at provider B does likewise.  Then we swap encrypted lists, and each encrypt the other guy's encrypted SSNs with our own keys.  Then we swap the doubly-encrypted lists.  Because the cipher is commutative, encrypting with key A first, and then key B should give the same results as encrypting with key B first and then key A.  Which means that any values that are shared on the two doubly-encrypted lists represent the same SSN, and therefore a shared patient.  So we know exactly who we share, without exposing the SSNs of our entire patient list.
To clarify a little, you need "encryption" that is commutative, deterministic (otherwise the commutative ciphertexts won't necessarily match even if the plaintexts do), and has a private encryption function (otherwise given that it is deterministic and the plaintext space is small, an exhaustive search would be possible). For example, Elgamal is commutative but it is also randomized and public key. Encryption is in quotes because, since you never decrypt, you actually just need a trapdoor function with those properties.

Pohlig-Hellman and SRA are suitable.

As far as implementations go, I do not know of any. However Pohlig-Hellman would be easy to implement with just a number theory library (it is just a single modular exponentiation -- you don't need to decrypt in your application). If you have a DSA library that has a function to generate a public key from a secret key, you can use that as the encryption function. 

Similarly, SRA is just RSA with two key pairs. If you could call the key generate function of an RSA implementation is such a way as to get $e,d$ if you supply $p,q$, then that would work.

Both of these ciphers are old and were developed before certain attacks were known. For Pohlig-Hellman, you should work in a multiplicative subgroup and this requires encoding the plaintext. SRA could leak the Jacobi symbol of the plaintext like RSA (I think even if $e$ is not known?).

Finally, the application you are implementing is called "private set intersection." There are lots and lots of papers on how to do it, and potentially some implementations of the whole protocol. There are some issues with the way you are implementing it assuming that one of the parties is malicious. 

If both parties are honest (only submit true values) and fair (one party learns the result before the other), it seems ok. But there are all sorts of attacks otherwise that could be resolved by using a private set intersection protocol designed for exactly this purpose.