Cryptology ePrint Archive: Report 2019/175

The Communication Complexity of Threshold Private Set Intersection

Satrajit Ghosh and Mark Simkin

Abstract: Threshold private set intersection enables Alice and Bob who hold sets $A$ and $B$ of size $n$ to compute the intersection $A \cap B$ if the sets do not differ by more than some threshold parameter $t$. In this work, we investigate the communication complexity of this problem and we establish the first upper and lower bounds. We show that any protocol has to have a communication complexity of $\Omega(t)$. We show that an almost matching upper bound of $\tilde{\mathcal{O}}(t)$ can be obtained via fully homomorphic encryption. We present a computationally more efficient protocol based on weaker assumptions, namely additively homomorphic encryption, with a communication complexity of $\tilde{\mathcal{O}}(t^2)$. We show how our protocols can be extended to the multiparty setting. For applications like biometric authentication, where a given fingerprint has to have a large intersection with a fingerprint from a database, our protocols may result in significant communication savings. We, furthermore, show how to extend all of our protocols to the multiparty setting.

Prior to this work, all previous protocols had a communication complexity of $\Omega(n)$. Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter $t$ and only logarithmically on the set size $n$.

Category / Keywords: foundations / Communication Complexity, Private Set Intersection, Multiparty

Original Publication (with minor differences): IACR-CRYPTO-2019

Date: received 18 Feb 2019, last revised 27 May 2020

Contact author: satrajit at cs au dk,simkin@cs au dk

Available format(s): PDF | BibTeX Citation

Note: Minor issue fixed.

Version: 20200527:210518 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]