is there a problem with the following private set intersection protocol

Question

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.

Answer 1

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})$.