Welcome to the resource topic for 2020/1307
Title:
Multiparty Cardinality Testing for Threshold Private Set Intersection
Authors: Pedro Branco, Nico Döttling, 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).
ePrint: https://eprint.iacr.org/2020/1307
Talk: https://www.youtube.com/watch?v=cpGbpCsk2ak
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .