Suppose both I and my friend have a set of integer numbers. We want to know the number of common elements in our two sets but without knowing elements of the sets of each other. So I don't want my friend to know any element of my set and he don't want me to know his. But we want to know how many elements are in the intersection of our two sets (without also knowing which elements these are).

Are there any algorithm to achieve this goal? One that will calculate the number of common elements using data from which it is very difficult to compute elements of our sets? Or its just impossible?

All elements of our sets are integers so we can use algorithms of computational number theory.


Answer. Yes! It is possible to do this, using the magic of secure multi-party computation. The security property we get is basically the best one could possibly hope for: namely, your friend learns nothing more about your set of numbers than the maximum he could have learned by choosing his set in a clever way and learning the size of the intersection; and your friend gets symmetrical protection against you.

The particular problem you list is known as the cardinality set intersection problem or cardinality private set intersection problem, and there has been considerable research on protocols for this problem.

One way to solve this problem is using the standard general-purpose machinery for secure two-party computation. The general-purpose tools for secure two-party computation can be applied directly to this problem, giving one way to do what you want.

Alternatively, researchers have devised special-purpose protocols designed especially to solve the cardinality set intersection problem. These special-purpose protocols are considerably more efficient than what you get if you apply the general-purpose methods. Here are some some pointers into the research literature in this area:

Mathematical details. Here's the basic idea behind Kissner and Song's approach:

  1. They encode each set as a polynomial: for example, the set $S = \{3,5,17\}$ is encoded as the polynomial $s(x) = (x-3)(x-5)(x-17)$, the set $T = \{4,12,17\}$ is represented as $t(x) = (x-4)(x-12)(x-17)$, and so on. In general, a polynomial $p(x)$ represents the set of roots of $p(x)$, i.e., the set $\{a : p(a)=0\}$.

  2. Given polynomials $s(x)$,$t(x)$ representing the sets $S,T$, we can compute a polynomial $u(x)$ representing the intersection $U = S \cap T$, by picking random polynomials $q(x),r(x)$ and computing

    $$u(x) = q(x)s(x) + r(x)t(x)$$

    Note that the roots of $u(x)$ are (with high probability) exactly the common roots of $s(x)$,$t(x)$, i.e., $u(a)=0$ usually happens only when $s(a)=t(a)=0$

    For example, if with sets $S,T$ defined as in 1 above, we might pick $q(x) = 2x^3 + 7x^2 + x - 3$ and $r(x) = 14x^3 + 3x^2 - 2x + 5$. Then we can calculate $u(x) = 16 x^6 - 502 x^5 + ... - 3315$, whose only integer root is $x=17$. This corresponds to the fact that $U = S \cap T = \{17\}$.

  3. They use Pallier's additively homomorphic public-key encryption scheme. In particular, you and your friend jointly generate a Paillier public/private keypair, so that both of you know the public key but the private key is shared between you (it is only possible to decrypt if both of you jointly participate). There are known ways to do this.

  4. You take your set $S$, encode it as a polynomial $s(x)$, and encrypt each coefficient under the Paillier public key, and send the resulting encrypted polynomial to your friend. Your friend takes his set $T$, encodes it as a polynomial $t(x)$, encrypt each coefficient under the Paillier public key, and send the resulting encrypted polynomial to you. You jointly generate random polynomials $q(x),r(x)$ (there are known ways to do this). Then, using the additively homomorphic properties of Paillier encryption, you can both compute an encrypted form of the polynomial $u(x) = q(x)s(x) + r(x)t(x)$, where you get the encrypted value of each coefficient of $u(x)$. You each share the value of $u(x)$ you got with the other person.

  5. For each element $a$ of your set $S$, you evaluate the encrypted polynomial at $a$, thus learning the encryption of $u(a)$, call it $E(u(a))$ (the additively homomorphic properties of Paillier encryption allow you to do this), and then you pick a random non-zero value $c$ and multiply to get $E(c*u(a))$. You do this separately for each element of your set, so you get $|S|$ encrypted values, you shuffle them, and send them to your friend. Your friend does the same with his set and sends you a shuffled set of $|T|$ encrypted values.

    In the running example, you'd learn the encryption of $u(3)$, $u(5)$, and $u(17)$, you'd pick random non-zero values, say $8$, $2$, $5$, and you'd share $E(8\cdot u(3))$, $E(2\cdot u(5))$, and $E(5 \cdot u(17))$ with your friend in random order. In this case $u(3)=-50904$, $u(5)=152880$, $u(17)=0$, so you'd be sharing $E(8\cdot-50904)$, $E(2\cdot152880)$, and $E(0)$, in random order. Your friend would do something similar with his set.

  6. Finally, you and your friend jointly decrypt the encrypted values you've shared with each other, using the shared private key. You count how many zeros you see in the decrypted values your friend sent you. Your friend counts how many zeros are present in the decrypted values you sent him. This is the number of values you had in common, i.e., the cardinality of $|S \cap T|$.

I've introduced some simplifications (e.g., all computations have to be done in an appropriate group, and many others). Please don't try to implement based upon this description alone. See Kissner and Song's paper for the full details. You might also look into the subsequent literature; there have been some follow-on papers that claim to improve their scheme to get better performance, though I'm not familiar with all the details. Also, in a real implementation, you'd need to add some zero-knowledge proofs at each step, to prove that each participant correctly performed their own computation (i.e., to lift from the honest-but-curious model to the malicious model). There has been follow-on research on that problem as well.

Summary. As you can see, this gets highly technical -- but the bottom line is that this problem has been studied in detail before, and there exist clever, beautiful, efficient solutions to it.

| improve this answer | |

Not a complete answer, but it seems like the possible range of numbers needs to be very large and the actual numbers highly unpredictable. Otherwise, regardless of the specific algorithm, your "friend" could claim to have many or all of the numbers in his set and then learn information about how many you have in yours. If you were willing to perform the experiment repeatedly (and most automated systems are) the friend could learn your numbers through iterative refinement.

| improve this answer | |
  • 1
    $\begingroup$ Yes, this is unavoidable. However: it is possible to limit the information leakage, simply by limiting the number of times you will run the protocol. Moreover: There exist protocols that achieve the best security that is achievable, i.e., that leak nothing more than this information (a fact that I find rather amazing and beautiful). See my answer. $\endgroup$ – D.W. Aug 18 '11 at 7:44

How about this idea:

  • We'll assume that the integers in the sets are all in the range $[2, N]$ for some agreed-upon $N$. (why is the start of the range $2$? Because the below protocol doesn't work with the element $1$; if the set has a different range, it is straight-forward to have a public mapping between the values that the set can be, and the range $[2, N]$, if need be)

We'll call side 1's set $E_i$, and side 2's set $F_i$.

  • Both sides agree on a prime $p$ with the properties:
    • Both $p$ and $\frac{p-1}{2}$ are prime
    • $\frac{p-1}{2}>N$
    • $p$ is large enough that the decisional Diffie-Hellman problem is infeasible (decisional DH problem? Well, if the dDH problem was feasible, someone could attempt to attempt to use it to find matching pairs).

Phase 1:

  • Side 1 selects a random value $1 \leq e < \frac{p-1}{2}$, computes the values $P_i = (E_i)^{2e} \mod p$, shuffles those values into random order, and sends those values to side 2. (why $2e$? Well, it's so that someone won't be able to use whether the elements were Quadratic Residues as a tag)

  • Similarly, side 2 selects a random $1 \leq f < \frac{p-1}{2}$, computes the values $Q_i = (F_i)^{2f} \mod p$, shuffles those values, and sends those values to side 1.

Phase 2:

  • Side 1 takes the values it gets from side 2 $Q_i$, computes $R_i = (Q_i)^e \mod p$, shuffles those values into random order, and sends those values to side 2

  • Similarly, side 2 takes the values it gets from side 1 $P_i$, computes $S_i = (P_i)^f \mod p$, shuffles those values into random order, and sends those values to side 1.

  • Both sides count how many values occur in common between $R_i$ and $S_i$; that's how many common elements there were in the original sets.

| improve this answer | |
  • $\begingroup$ A very clever attempt!, but unfortunately your scheme is not secure: it leaks partial information about the sets. For instance, if side 1's set is of the form {a,a^2}, then side 2 can learn this fact (by noticing that P_2 = (P_1)^2 mod p). Or if side 1's set is of the form {a,b,a*b}, then side 2 can detect this. I don't know if this is the only weakness, but in many applications it will probably be enough to reject the protocol. Fortunately, there exist solutions that don't have this weakness; see my answer. $\endgroup$ – D.W. Aug 18 '11 at 7:49

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.