Compact and Malicious Private Set Intersection for Small Sets

Mike Rosulek; Ni Trieu

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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}
}