The Communication Complexity of Threshold Private Set Intersection

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

DOI

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.

OriginalsprogEngelsk
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
Vol/bindII
UdgivelsesstedCham
ForlagSpringer
Udgivelsesår2019
Sider3-29
ISBN (trykt)9783030269500
ISBN (Elektronisk)978-3-030-26951-7
DOI
StatusUdgivet - 2019
Begivenhed39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, USA
Varighed: 18 aug. 201922 aug. 2019

Konference

Konference39th Annual International Cryptology Conference, CRYPTO 2019
LandUSA
BySanta Barbara
Periode18/08/201922/08/2019
SponsorCalibra, Cloudflare, Concordium, Conflux, et al., Fujitsu
SerietitelLecture Notes in Computer Science
Vol/bind11693
ISSN0302-9743

Se relationer på Aarhus Universitet Citationsformater

ID: 176198505