Paper 2021/122

PSImple: Practical Multiparty Maliciously-Secure Private Set Intersection

Aner Ben Efraim, Olga Nissenbaum, Eran Omri, and Anat Paskin-Cherniavsky

Abstract

Private set intersection (PSI) protocols allow a set of mutually distrustful parties, each holding a private set of items, to compute the intersection over all their sets, such that no other information is revealed. PSI has a wide variety of applications including online advertising (e.g., efficacy computation), security (e.g., botnet detection, intrusion detection), proximity testing (e.g., COVID-19 contact tracing), and more. Private set intersection is a rapidly developing area and there exist many highly efficient protocols. However, almost all of these protocols are for the case of two parties or for semi-honest security. In particular, despite the high interest in this problem, prior to our work there has been no concretely efficient, maliciously secure multiparty PSI protocol. We present PSImple, the first concretely efficient maliciously-secure multiparty PSI protocol. Our construction is based on oblivious transfer and garbled Bloom filters. To demonstrate the practicality of the PSImple protocol, we implemented the protocol and ran experiments with up to $32$ parties and $2^{20}$ inputs. We show that PSImple is competitive even with the state-of-the-art concretely efficient semi-honest multiparty PSI protocols. Additionally, we revisit the garbled Bloom filter parameters used in the 2-party PSI protocol of Rindal and Rosulek (Eurocrypt 2017). Using a more careful analysis, we show that the size of the garbled Bloom filters and the number of oblivious transfers required for malicious security can be significantly reduced, often by more than $20\%$. These improved parameters can be used both in the 2-party PSI protocol of Rindal and Rosulek and in PSImple.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Private set intersectionConcrete efficiencyMalicious security
Contact author(s)
omrier @ gmail com
anermosh @ post bgu ac il
olga @ nissenbaum ru
anps83 @ gmail com
History
2021-05-13: revised
2021-02-05: received
See all versions
Short URL
https://ia.cr/2021/122
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/122,
      author = {Aner Ben Efraim and Olga Nissenbaum and Eran Omri and Anat Paskin-Cherniavsky},
      title = {PSImple: Practical Multiparty Maliciously-Secure Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2021/122},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/122}},
      url = {https://eprint.iacr.org/2021/122}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.