Privacy-Preserving Set Operations

Lea Kissner, Carnegie Mellon University

Private computation over sets is an important problem. In many applications, each party has its own private input set, and multiple parties need to collectively compute a certain function of their private input sets in a privacy-preserving manner, that is, no party learns more information about other parties' private input sets than what can be deduced from the result.

In this paper, we propose efficient techniques for privacy-preserving operations on multisets. By building a framework of set operations using polynomial representations and employing the mathematical properties of polynomials, we design efficient methods to enable privacy-preserving computation of the union, intersection, and element reduction operations.

An important feature of our privacy-preserving set operations is that they can be arbitrarily composed, and thus used in a wide range of applications. To demonstrate the power of our techniques, we apply our operations to solve specific problems, including multi-party Set-Intersection and Over-Threshold Set-Union, as well as determining the Subset relation. Our results are more efficient than previous work and are provably secure in the standard adversary models.

Gates 4B (opposite 490) Thursday 03/10/05 1630 hrs