Welcome to the resource topic for 2019/175
Title:
The Communication Complexity of Threshold Private Set Intersection
Authors: Satrajit Ghosh, 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.
ePrint: https://eprint.iacr.org/2019/175
Talk: https://www.youtube.com/watch?v=_B1FFf-ot8g
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .