1
$\begingroup$

Say Alice has the following set: $\{A_1,A_2,\ldots,An\}$
and Bob has the following set: $\{B_1,B_2,\ldots,B_m\}$

Alice creates a key $a$ and bob creates a key $b$
these keys should be commutative (eg: use RSA)

Alice encrypts each element of her set with $a$ to create $\{A_{1'},A_{2'}, \ldots,A_{n'}\}$
and similarly Bob makes $\{B_{1'},B_{2'},\ldots,B_{m'}\}$ with $b$

Alice sends her set to Bob and Bob sends his to Alice.
Alice encrypts each element of $\{B_{1'},B_{2'},\ldots,B_{m'}\}$ with a to make $\{B_{1"},B_{2"},\ldots,B_{m"}\}$ and similarly Bob makes $\{A_{1"},A_{2"},\ldots,A_{n"}\}$

Now Alice sends $\{B_{1"},B_{2"},\ldots,B_{m"}\}$ to Bob and Bob sends $\{A_{1"},A_{2"},\ldots,A_{n"}\}$ to Alice.

Because the keys commute, if $Bi=Aj$ for some $i$ and $j$, then $Bi" = Aj"$
Thus Alice and Bob can each identify which elements they have in common.

Also this protocol only requires encrypting and communicating each element twice so it has $O(n+m)$ run time.

I have not been able to find this protocol anywhere and it seems very simple so I thought there must be a problem with it.

$\endgroup$
  • $\begingroup$ RSA does not have the commutative property, because the keys have to have different moduli. If they had the same modulus, both parties could calculate the other parties private key from their own key pair. You could use ElGamal on the same group. $\endgroup$ – tylo Jun 27 '19 at 6:44
  • $\begingroup$ Where did you come across this protocol? It might be useful to check the source of it. $\endgroup$ – zetaprime Jun 27 '19 at 9:26
1
$\begingroup$

This is very similar to a well-known protocol that dates back to the following work.

Catherine Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy. 1986

Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing Privacy and Trust in Electronic Communities. In ACM Conference on Electronic Commerce. 1999

It uses the commutative property, namely that $(x^a)^b = (x^b)^a$. This PSI protocol is usually used with the following modifications:

  1. Usually Diffie-Hellman cyclic groups are used rather than RSA. This allows you to send around compact elliptic curve elements (e.g., 256 bits) instead of RSA group elements (e.g., 2048 bits). Diffie-Hellman groups clearly give you the commutative property that this protocol requires.

    Also, RSA is commutative only when using the same modulus. In this setting, who chooses the modulus? Probably neither party should know the factorization.

  2. It is not secure to exponentiate the raw items. Instead, they should be hashed under a random oracle first.

    Consider if Alice holds items $x, x^2, x^3, \ldots$ and Bob only holds item $x$. Then Bob will eventually learn $x^{ab}, (x^2)^{ab}, (x^3)^{ab}, \ldots$. He will recognize $x^{ab}$ because he has item $x$ (this is what we expect). But he can also recognize the other values as $(x^{ab})^2, (x^{ab})^3, \ldots$, and conclude which of $x^2, x^3, \ldots$ Alice holds. Clearly this is a violation of privacy.

    The parties should compute $H(x)^{ab}, H(x^2)^{ab}, H(x^3)^{ab}, \ldots$, where $H$ is a random oracle. $H$ breaks the algebraic relations among the items, so that knowing $H(x)^{ab}$ doesn't help you predict $H(x^2)^{ab}$.

  3. The RSA assumption and CDH assumptions give you the following property: "given $H(x_1)^{ab}, \ldots, H(x_n)^{ab}$ for random/secret $a$, it is hard to compute $H(x^*)^{ab}$ for $x^* \not\in\{x_1, \ldots, x_n\}$." This is not quite enough for security of the PSI protocol. We in fact need $H(x^*)^{ab}$ to be pseudorandom given $H(x_1)^{ab}, \ldots, H(x_n)^{ab}$ (not just hard to compute). This can be achieved by assuming DDH rather than CDH, or by applying an additional random oracle, so that Alice sends values of the form $H'(H(x)^{ab})$.

$\endgroup$
  • $\begingroup$ to construct the random oracle could I have both parties pick a random string, have them concatenate the strings, then use the following function H(x) = hash(x+string) where hash is some cryptographic hash function such as sha256? I think this would be fine because neither party can know the function H before the algorithm is performed. I would do similarly for H'. $\endgroup$ – user11466558 Jun 26 '19 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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