The Communication Complexity of Threshold Private Set Intersection

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer 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.

TitelAdvances in Cryptology – CRYPTO 2019 : 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings
RedaktørerAlexandra Boldyreva, Daniele Micciancio
Antal sider27
ISBN (trykt)9783030269500
ISBN (Elektronisk)978-3-030-26951-7
StatusUdgivet - 2019
Begivenhed39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, USA
Varighed: 18 aug. 201922 aug. 2019


Konference39th Annual International Cryptology Conference, CRYPTO 2019
BySanta Barbara
SponsorCalibra, Cloudflare, Concordium, Conflux, et al., Fujitsu
SerietitelLecture Notes in Computer Science

Se relationer på Aarhus Universitet Citationsformater

ID: 176198505