International Association
for Cryptologic Research

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. In this work, we present a Threshold PSI scheme for $N$ parties with communication complexity $\tilde O(Nt^2)$. At the heart of our construction is a new cardinality-test protocol, which allows the parties to determine if the intersection of their sets is sufficiently large.