SoK

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

Conference Paper (2024)
Author(s)

J.V. Vos (TU Delft - Cyber Security)

Mauro Conti (UniversitĂ  degli Studi di Padova, TU Delft - Cyber Security)

Zekeriya Erkin (TU Delft - Cyber Security)

Research Group
Cyber Security
DOI related publication
https://doi.org/10.1109/SP54263.2024.00079
More Info
expand_more
Publication Year
2024
Language
English
Research Group
Cyber Security
Pages (from-to)
465-483
ISBN (electronic)
9798350331301
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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.

Files

SoK_Collusion-resistant_Multi-... (pdf)
(pdf | 1.22 Mb)
- Embargo expired in 10-03-2025
License info not available