CryptoDB

Paper: The Communication Complexity of Threshold Private Set Intersection

Authors: Satrajit Ghosh Mark Simkin DOI: 10.1007/978-3-030-26951-7_1 Search ePrint Search Google 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.
BibTeX
@article{crypto-2019-29880,
title={The Communication Complexity of Threshold Private Set Intersection},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11693},
pages={3-29},
doi={10.1007/978-3-030-26951-7_1},
author={Satrajit Ghosh and Mark Simkin},
year=2019
}