Compact and Malicious Private Set Intersection for Small Sets

Mike Rosulek; Ni Trieu

Paper 2021/1159

Compact and Malicious Private Set Intersection for Small Sets

Mike Rosulek and Ni Trieu

Abstract

We describe a protocol for two-party private set intersection (PSI) based on Diffie-Hellman key agreement. The protocol is proven secure against malicious parties, in the ideal permutation + random oracle model. For small sets (500 items or fewer), our protocol requires the least time and communication of any known PSI protocol, even ones that are only semi-honest secure and ones that are not based on Diffie-Hellman. It is one of the few significant improvements to the 20-year old classical Diffie-Hellman PSI protocol of Huberman, Franklin, and Hogg (ACM Elec. Commerce 1999). Our protocol is actually a generic transformation that constructs PSI from a class of key agreement protocols. This transformation is inspired by a technique of Cho, Dachman-Soled, and Jarecki (CT-RSA 2016), which we streamline and optimize in several important ways to achieve our superior efficiency.

Note: Oct 2021: Fixed a bug in the security proof for the semi-honest protocol variant, added a second semi-honest protocol variant that does not require an ideal permutation, corrected the communication cost of our protocol (Table 3, row 9 & row 12)

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. ACM CCS 2021
DOI: 10.1145/3460120.3484778
Keywords: private set intersection
Contact author(s): rosulekm @ eecs oregonstate edu
nitrieu @ asu edu
History: 2021-10-18: last of 2 revisions; 2021-09-14: received; See all versions
Short URL: https://ia.cr/2021/1159
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1159,
      author = {Mike Rosulek and Ni Trieu},
      title = {Compact and Malicious Private Set Intersection for Small Sets},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1159},
      year = {2021},
      doi = {10.1145/3460120.3484778},
      note = {\url{https://eprint.iacr.org/2021/1159}},
      url = {https://eprint.iacr.org/2021/1159}
}