Oblivious Decryption: Decrypting with a private key, without knowing the message 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?
This can be done by exploiting the homomorphic property of RSA.  Let's say Alice's key is $(e,N,d)$ where $e$ is the public exponent, $N$ the modulus, and $d$ the private exponent.

To decrypt $x$, Bob samples $r$ randomly from $\{1,\cdots,N\}$ and computes $xr^e\mod N$ and sends it to Alice.  Alice computes $(xr^e)^d=x^dr\mod N$ and sends it back to Bob.  Bob multiplies by $r^{-1}$ to extract $x^d$.

Note that Alice does not know $r$ and thus cannot determine $x^d$ from $x^dr$.  This does lead to at least one vulnerability: Bob can send Alice whatever he likes.  In particular, he could ask for the decryptions of other private messages to Alice that he somehow acquired.