### Multi-Party Threshold Private Set Intersection with Sublinear Communication

Saikrishna Badrinarayanan, Peihan Miao, Srinivasan Raghuraman, 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 $\widetilde{O}(nT)$ under a weaker assumption of threshold additive homomorphic encryption. As a direct implication, we solve one of the open problems in the work of Ghosh and Simkin (CRYPTO 2019) by designing a two-party protocol with communication cost $\widetilde{O}(T)$ from assumptions weaker than FHE. As a consequence of our results, 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
A minor revision of an IACR publication in PKC 2021
Keywords
Private Set IntersectionCommunication ComplexityMultiparty Computation
Contact author(s)
sabadrin @ visa com
peihan @ uic edu
srraghur @ visa com
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

BibTeX

@misc{cryptoeprint:2020/600,
author = {Saikrishna Badrinarayanan and Peihan Miao and Srinivasan Raghuraman and Peter Rindal},
title = {Multi-Party Threshold Private Set Intersection with Sublinear Communication},
howpublished = {Cryptology ePrint Archive, Paper 2020/600},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/600}},
url = {https://eprint.iacr.org/2020/600}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.