Paper 2020/600

Multi-Party Threshold Private Set Intersection with Sublinear Communication

Saikrishna Badrinarayanan, Peihan Miao, Srinivasan Raghuraman, and Peter Rindal


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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2021
Private Set IntersectionCommunication ComplexityMultiparty Computation
Contact author(s)
sabadrin @ visa com
peihan @ uic edu
srraghur @ visa com
perindal @ visa com
2021-03-01: last of 2 revisions
2020-05-22: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.