Paper 2021/1159 Original: eprint.iacr.org/2021/1159 ↗
Compact and Malicious Private Set Intersection for Small Sets
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2021-10-18: last updated
- 2021-09-14: published
- Short URL
- https://ia.cr/2021/1159
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2021/1159}
}