**Multiparty Cardinality Testing for Threshold Private Set Intersection**

*Pedro Branco and 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)$.

**Category / Keywords: **cryptographic protocols / threshold private set intersection,

**Date: **received 19 Oct 2020, last revised 21 Oct 2020

**Contact author: **pedrodemelobranco at gmail com,nico doettling@gmail com,sihang pu@gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20201021:081900 (All versions of this report)

**Short URL: **ia.cr/2020/1307

[ Cryptology ePrint archive ]