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.
Category / Keywords: cryptographic protocols / Private set intersection; Concrete efficiency; Malicious security; Date: received 2 Feb 2021, last revised 2 Feb 2021 Contact author: omrier at gmail com,anermosh@post bgu ac il,olga@nissenbaum ru,anps83@gmail com Available format(s): PDF | BibTeX Citation Version: 20210205:123515 (All versions of this report) Short URL: ia.cr/2021/122