Suppose both I and my friend have a set of integer numbers. We want to know the
ID: 651388 • Letter: S
Question
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.
Explanation / Answer
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:
Lea Kissner, Dawn Song, Privacy-Preserving Set Operations, CRYPTO 2005.
Yingpeng Sang, Hong Shen, Efficient and Secure Protocols for Privacy Preserving Set Operations, ACM TISSEC 2009. (Improves upon Kissner-Song.)
Michael J. Freedman, Kobbi Nissim, Benny Pinks, Efficient private matching and set intersection, EUROCRYPT 2004. (An alternative to Kissner-Song.)
Carmit Hazay, Kobbi Nissim, Efficient Set Operations in the Presence of Malicious Adversaries, PKC 2010. (Improves upon Freedman-Nissim-Pinks in the malicious model.)
Dana Dachman-Soled, Tal Malkin, Mariana Raykova, Moti Yung, Efficient Robust Private Set Intersection, ACNS 2009. (Addresses the malicious model.)