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)$. 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.

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

Date: received 18 Feb 2019, last revised 26 Feb 2019

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

Available format(s): PDF | BibTeX Citation

Version: 20190226:070303 (All versions of this report)

Short URL: ia.cr/2019/175


[ Cryptology ePrint archive ]