I've got an application (detailed below) that calls for the use of a cipher that is commutative. I've been doing some googling & 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 & 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 & 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.