Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / private set intersection

Original Publication (in the same form): ACM CCS 2021
DOI:
10.1145/3460120.3484778

Date: received 10 Sep 2021

Contact author: rosulekm at eecs oregonstate edu, nitrieu at asu edu

Available format(s): PDF | BibTeX Citation

Version: 20210914:175050 (All versions of this report)

Short URL: ia.cr/2021/1159


[ Cryptology ePrint archive ]