I’m trying to devise a protocol, complimentary to a private-set-intersection, involving three parties, namely Alice, Bob and Charlie.
Alice has a public and a private key. And receives website logs from Charlie.
Charlie runs a website, and he sends his website logs to Alice, encrypting the user-ids using Alice’s public key. Let’s say they are using RSA with padding for each log entry, this way the same user-id always looks random when encrypted.
Bob is managing a small part of Charlie’s website. Charlie has agreed to forward a related portion of the logs to Bob. But it’s directly sampled from the same logs Alice got, so they carry the user-ids encrypted with Alice’s public key.
Naturally, Bob doesn’t have Alice’s private key, and wants to learn the user-ids that visited his section. He can ask Alice to decrypt the user-ids he has, however he doesn’t want to give Alice the information about the users he’s interested in.
Is it possible to devise a protocol where Alice decrypts the messages encrypted by her public key, without really knowing what the message was. Hence the name Oblivious Decryption...
So, I have thought of the commutative property of RSA. If Bob had a private and public key both secret to himself, before sending the message to Alice he might have encrypted and then decrypt what Alice has decrypted, getting access to the user-id himself only. However for Bob to be able to create such a key-pair he needs to know the prime factors of the modulus.
Is there a way, this can be achieved. And If not can we prove that this is not possible?