Paper 2022/573
Finding One Common Item, Privately
Abstract
Private set intersection (PSI) allows two parties, who each hold a set of items, to learn which items they have in common, without revealing anything about their other items. Some applications of PSI would be better served by revealing only one common item, rather than the entire set of all common items. In this work we develop simple special-purpose protocols for privately finding one common item (FOCI) from the intersection of two sets. The protocols differ in how that item is chosen --- e.g., uniformly at random from the intersection; the "best" item in the intersection according to one party's ranking; or the "best" item in the intersection according to the sum of both party's scores. All of our protocols are proven secure against semi-honest adversaries, under the Decisional Diffie-Hellman (DDH) assumption and assuming a random oracle. All of our protocols leak a small amount of information (e.g., the cardinality of the intersection), which we precisely quantify.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. SCN 2022
- Keywords
- private set intersection
- Contact author(s)
-
trb4137 @ truman edu
janabel @ mit edu
rosulekm @ eecs oregonstate edu - History
- 2022-07-04: revised
- 2022-05-16: received
- See all versions
- Short URL
- https://ia.cr/2022/573
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/573,
author = {Tyler Beauregard and Janabel Xia and Mike Rosulek},
title = {Finding One Common Item, Privately},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/573},
year = {2022},
url = {https://eprint.iacr.org/2022/573}
}
