Abstract:
Multi-party computation (MPC) allows parties to interact with cloud-based data and services while maintaining privacy and confidentiality of their private data. As a special case of MPC, private set intersection (PSI) protocols focus on securely computing the intersection between a server and a client of their private set. Our research extends the threshold functionality for PSI within the realm of cloud computing, where the server possesses a larger set than the client. This paper fills this gap by proposing new private intersection cardinality (PSI-CA) protocol, and more broadly, threshold private set intersection (tPSI) protocol using fully homomorphic encryption (FHE). In tPSI protocol, two parties holding two private sets collaboratively compute the intersection and reveal the result if and only if the size of the intersection exceeds some predefined threshold. In this process, no other information, in particular, elements not in the intersection remain hidden. The problem of PSI-CA and tPSI has many applications in online collaboration, e.g., fingerprint matching, online dating, and ride sharing.
At a high level, we use FHE to encrypt a Bloom filter (BF) that encodes the small set and homomorphically check whether the elements in the larger set belongs to the small set, e.g., homomorphic membership test. Counting the number of positive membership directly already yields a PSI-CA protocol with optimal asymptotic communication complexity Ω(n) = Ω(min(N, n)), where N (resp. n) is the size of the large (resp. small) set. To construct a tPSI protocol, we develop a novel secret token generation protocol: a shared secret token is generated if and only if the intersection size satisfies the threshold condition, by exploiting the programmable bootstrapping technique in FHE. This new secret token generation protocol, when composed with any standard PSI protocol, yields a tPSI with the same asymptotic communication complexity as the chosen plain PSI.
Along the way, we develop specific FHE optimizations that might be of independent interest. These optimizations overcome the weakness of low precision in programmable bootstrapping. As a result, tPSI over relatively large sets can be supported.