Paper 2023/919

Threshold Private Set Intersection with Better Communication Complexity

Abstract

Given $\ell$ parties with sets $X_1,\dots ,X_{\ell }$ of size $n$, we would like to securely compute the intersection ${\cap }_{i=1}^{\ell }{X}_i$, if it is larger than $n-t$ for some threshold $t$, without revealing any other additional information. It has previously been shown (Ghosh and Simkin, Crypto 2019) that this function can be securely computed with a communication complexity that only depends on $t$ and in particular does not depend on $n$. For small values of $t$, this results in protocols that have a communication complexity that is sublinear in the size of the inputs. Current protocols either rely on fully homomorphic encryption or have an at least quadratic dependency on the parameter $$. In this work, we construct protocols with a quasilinear dependency on $$ from simple assumptions like additively homomorphic encryption and oblivious transfer. All existing approaches, including ours, rely on protocols for computing a single bit, which indicates whether the intersection is larger than $$ without actually computing it. Our key technical contribution, which may be of independent interest, takes any such protocol with secret shared outputs and communication complexity $$, where $$ is the security parameter, and transforms it into a protocol with communication complexity $$.