CryptoDB
The Communication Complexity of Threshold Private Set Intersection
| Authors: | |
|---|---|
| Download: |
|
| 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
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
}