Paper 2020/1307

Multiparty Cardinality Testing for Threshold Private Set Intersection

Pedro Branco, Nico Döttling, and Sihang Pu

Abstract

Threshold Private Set Intersection (PSI) allows multiple parties to compute the intersection of their input sets if and only if the intersection is larger than $n-t$, where $n$ is the size of the sets and $t$ is some threshold. The main appeal of this primitive is that, in contrast to standard PSI, known upper-bounds on the communication complexity only depend on the threshold $t$ and not on the sizes of the input sets. Current Threshold PSI protocols split themselves into two components: A Cardinality Testing phase, where parties decide if the intersection is larger than some threshold; and a PSI phase, where the intersection is computed. The main source of inefficiency of Threshold PSI is the former part. In this work, we present a new Cardinality Testing protocol that allows $N$ parties to check if the intersection of their input sets is larger than $n-t$. The protocol incurs in $\tilde{ \mathcal{O}} (Nt^2)$ communication complexity. We thus obtain a Threshold PSI scheme for $N$ parties with communication complexity $\tilde{ \mathcal{O}}(Nt^2)$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2021
Keywords
threshold private set intersection
Contact author(s)
pedrodemelobranco @ gmail com
nico doettling @ gmail com
sihang pu @ gmail com
History
2021-03-01: last of 2 revisions
2020-10-20: received
See all versions
Short URL
https://ia.cr/2020/1307
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1307,
      author = {Pedro Branco and Nico Döttling and Sihang Pu},
      title = {Multiparty Cardinality Testing for Threshold Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1307},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1307}},
      url = {https://eprint.iacr.org/2020/1307}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.