Aarhus University Seal / Aarhus Universitets segl

The Communication Complexity of Threshold Private Set Intersection

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Threshold private set intersection enables Alice and Bob who hold sets (formula presented) and (formula presented) of size n to compute the intersection (formula presented) 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 (formula presented). We show that an almost matching upper bound of (formula presented) 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 (formula presented). 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 (formula presented). 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2019 : 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings
EditorsAlexandra Boldyreva, Daniele Micciancio
Number of pages27
Place of publicationCham
Publication year2019
ISBN (print)9783030269500
ISBN (Electronic)978-3-030-26951-7
Publication statusPublished - 2019
Event39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States
Duration: 18 Aug 201922 Aug 2019


Conference39th Annual International Cryptology Conference, CRYPTO 2019
LandUnited States
BySanta Barbara
SponsorCalibra, Cloudflare, Concordium, Conflux, et al, Fujitsu
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 176198505