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 ????−????, where n is the size of each set 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 ????−????. The protocol incurs in ????̃(????????2) communication complexity. We thus obtain a Threshold PSI scheme for N parties with communication complexity ????̃(????????2).
2021-05
2024-07-26