1
$\begingroup$

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?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I've just implemented a test for this, seems to work. However can you tell anything about the security of this? Can one factor $x^dr$ to get the $x^d$ value? $\endgroup$
    – zetaprime
    Oct 3, 2018 at 12:50
  • $\begingroup$ see crypto.stackexchange.com/questions/62846/… for the question I have asked related to the security of this. $\endgroup$
    – zetaprime
    Oct 3, 2018 at 13:34
  • $\begingroup$ Since we are working over a field, $x^dr$ does not have a unique factorization. In fact, for every sequence $a_1,a_2,\cdots, a_{k-1}$ that are relatively prime to $N$, there exists an $a_k$ such that $a_1\cdot a_2, \cdots a_{k}=x^dr$. Thus 'factorization' yields no useful information. $\endgroup$
    – rikhavshah
    Oct 3, 2018 at 15:31
  • $\begingroup$ can we conclude that, the extraction of $r$ and $x^d$ from the multiplication $x^dr$ is essentially equivalent to the discrete log problem? $\endgroup$
    – zetaprime
    Oct 3, 2018 at 16:26
1
$\begingroup$

For each user-id, Charlie can perform the first half of a Diffie Hellman exchange with Alice using an ephemeral keypair. Charlie will then use a symmetric cypher to encrypt the user-id, using as a key the cryptographic hash of the shared secret that is established via this DH exchange. The logs will include the encrypted user-ids as well as the ephemeral public key for each encrypted user-id.

Alice will use her private key and the ephemeral public key for each record to determine the shared secret to decrypt each user-id. Alice will send all shared secrets to Bob.

Bob can then use this list of shared secrets to decrypt the user-ids that are in his subset of the logs.

In order to avoid leaking the total number of user-ids in her log files, Alice could transmit to Bob a randomly ordered list of: (Hash(shared secret), Hash(encrypted user-id)). Alice can generate a large volume of dummy data to include in this list, so that Bob could tell the upper-bound of the number of user-ids in Alice's logs, but not exactly how many.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.