Paper 2020/600
Multi-Party Threshold Private Set Intersection with Sublinear Communication
Saikrishna Badrinarayanan and Peihan Miao and Peter Rindal
Abstract
In multi-party threshold private set intersection (PSI), $n$ parties each with a private set wish to compute the intersection of their sets if the intersection is sufficiently large. Previously, Ghosh and Simkin (CRYPTO 2019) studied this problem for the two-party case and demonstrated interesting lower and upper bounds on the communication complexity. In this work, we investigate the communication complexity of the multi-party setting $(n \geq 2)$. We consider two functionalities for multi-party threshold PSI. In the first, parties learn the intersection if each of their sets and the intersection differ by at most $T$. In the second functionality, parties learn the intersection if the union of all their sets and the intersection differ by at most $T$. For both functionalities, we show that any protocol must have communication complexity $\Omega(nT)$. We build protocols with a matching upper bound of $O(nT)$ communication complexity for both functionalities assuming threshold FHE. We also construct a computationally more efficient protocol for the second functionality with communication complexity $\tilde{O}(nT^2)$ under a weaker assumption of threshold additive homomorphic encryption. As a consequence, we achieve the first "regular" multi-party PSI protocol where the communication complexity only grows with the size of the set difference and does not depend on the size of the input sets.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Private Set IntersectionCommunication ComplexityMultiparty Computation
- Contact author(s)
- sabadrin @ visa com,peihan @ berkeley edu,perindal @ visa com
- History
- 2021-03-01: last of 2 revisions
- 2020-05-22: received
- See all versions
- Short URL
- https://ia.cr/2020/600
- License
-
CC BY