Paper 2021/122

PSImple: Practical Multiparty Maliciously-Secure Private Set Intersection

Aner Ben Efraim and Olga Nissenbaum and 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. PSI 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, 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 protocol is based on garbled Bloom filters, extending the 2-party PSI protocol of Rindal and Rosulek (Eurocrypt 2017) and the semi-honestly secure multiparty protocol of Inbar, Omri, and Pinkas (SCN 2018). To demonstrate the practicality of the PSImple protocol, we implemented our protocol and ran experiments with on up to 32 parties and $2^{18}$ inputs. We incorporated several optimizations into our protocol, and compared our protocol with the 2-party protocol of Rindal and Rosulek and with the semi-honest protocol of Inbar et al. Finally, we also revisit the parameters used in previous maliciously secure PSI works based on garbled Bloom filters. Using a more careful analysis, we show that the size of the garbled Bloom filters and the required number of oblivious transfers can be significantly reduced, often by more than 20%. These improved parameters can be used both in our protocol and in previous maliciously secure PSI protocols based on garbled Bloom filters.