Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Private Set Intersection, Communication Complexity, Multiparty Computation

Date: received 20 May 2020, last revised 27 May 2020

Contact author: sabadrin at visa com,peihan@berkeley edu,perindal@visa com

Available format(s): PDF | BibTeX Citation

Version: 20200528:020102 (All versions of this report)

Short URL: ia.cr/2020/600


[ Cryptology ePrint archive ]