Paper 2010/512

Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity

Jung Hee Cheon, Stanislaw Jarecki, and Jae Hong Seo


Secure computation of the set intersection functionality allows $n$ parties to find the intersection between their datasets without revealing anything else about them. An efficient protocol for such task could have multiple potential applications, in commerce, health-care, and security. However, all currently known secure set intersection protocols for $n>2$ parties have computational costs that are quadratic in the (maximum) number of entries in the dataset contributed by each party, rendering secure computation of set intersection impractical on anything but small datasets. In this paper we describe the first multi-party protocol for securely computing the set intersection functionality with both the communication and the computation costs that are quasi-linear in the size of the datasets. Specifically, our protocols require $O(n^2k\lambda)$ bits of communication and $\tilde{O}(n^2\lambda+(n\lambda+n^2)k)$ group multiplications per player in the malicious adversary setting, where $k$ is the size of each dataset and $\lambda$ is security parameter. Our protocol follows the basic idea of the protocol proposed by Kissner and Song, but we gain efficiency by using different representation of the polynomials associated with users' datasets, and careful employment of algorithms that interpolate or evaluate polynomials on multiple points more efficiently.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Privacy-preserving set operationprivacy-preserving set intersection
Contact author(s)
jhsbhs @ gmail com
2010-10-07: received
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Stanislaw Jarecki and Jae Hong Seo},
      title = {Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2010/512},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.