Paper 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 AB 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 Ω(t). We show that an almost matching upper bound of 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 . 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 . Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter and only logarithmically on the set size .

Note: Minor issue fixed.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
Communication ComplexityPrivate Set IntersectionMultiparty
Contact author(s)
satrajit @ cs au dk
simkin @ cs au dk
History
2020-05-27: last of 7 revisions
2019-02-26: received
See all versions
Short URL
https://ia.cr/2019/175
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/175,
      author = {Satrajit Ghosh and Mark Simkin},
      title = {The Communication Complexity of Threshold Private Set Intersection},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/175},
      year = {2019},
      url = {https://eprint.iacr.org/2019/175}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.