International Association for Cryptologic Research

International Association
for Cryptologic Research


The Communication Complexity of Threshold Private Set Intersection

Satrajit Ghosh
Mark Simkin
DOI: 10.1007/978-3-030-26951-7_1 (login may be required)
Search ePrint
Search Google
Abstract: Threshold private set intersection enables Alice and Bob who hold sets $$S_{\mathsf {A}}$$ and $$S_{\mathsf {B}}$$ of size n to compute the intersection $$S_{\mathsf {A}} \cap S_{\mathsf {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 $$\varOmega (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 $$\varOmega (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.
Video from CRYPTO 2019
  title={The Communication Complexity of Threshold Private Set Intersection},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  author={Satrajit Ghosh and Mark Simkin},