CryptoDB
Multi-Party Threshold Private Set Intersection with Sublinear Communication
| Authors: | |
|---|---|
| Download: | |
| 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. |
Video from PKC 2021
BibTeX
@article{pkc-2021-30975,
title={Multi-Party Threshold Private Set Intersection with Sublinear Communication},
booktitle={Public-Key Cryptography - PKC 2021},
publisher={Springer},
doi={10.1007/978-3-030-75248-4_13},
author={Saikrishna Badrinarayanan and Peihan Miao and Srinivasan Raghuraman and Peter Rindal},
year=2021
}