Paper 2023/1777

SoK: Collusion-resistant Multi-party Private Set Intersections in the Semi-honest Model

Jelle Vos, Delft University of Technology
Mauro Conti, University of Padua, Delft University of Technology
Zekeriya Erkin, Delft University of Technology
Abstract

Private set intersection protocols allow two parties with private sets of data to compute the intersection between them without leaking other information about their sets. These protocols have been studied for almost 20 years, and have been significantly improved over time, reducing both their computation and communication costs. However, when more than two parties want to compute a private set intersection, these protocols are no longer applicable. While extensions exist to the multi-party case, these protocols are significantly less efficient than the two-party case. It remains an open question to design collusion-resistant multi-party private set intersection (MPSI) protocols that come close to the efficiency of two-party protocols. This work is made more difficult by the immense variety in the proposed schemes and the lack of systematization. Moreover, each new work only considers a small subset of previously proposed protocols, leaving out important developments from older works. Finally, MPSI protocols rely on many possible constructions and building blocks that have not been summarized. This work aims to point protocol designers to gaps in research and promising directions, pointing out common security flaws and sketching a frame of reference. To this end, we focus on the semi-honest model. We conclude that current MPSI protocols are not a one-size-fits-all solution, and instead there exist many protocols that each prevail in their own application setting.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. IEEE Security & Privacy (S&P) 2024
Keywords
Private Set IntersectionsSystematization of KnowledgePrivacy-Enhancing Technologies
Contact author(s)
J V Vos @ tudelft nl
conti @ math unipd it
Z Erkin @ tudelft nl
History
2023-11-17: approved
2023-11-16: received
See all versions
Short URL
https://ia.cr/2023/1777
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2023/1777,
      author = {Jelle Vos and Mauro Conti and Zekeriya Erkin},
      title = {{SoK}: Collusion-resistant Multi-party Private Set Intersections in the Semi-honest Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1777},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1777}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.