Federated K-Private Set Intersection

Private set intersection (PSI) is a popular protocol that allows multiple parties to evaluate the intersection of their sets without revealing them to each other. PSI has numerous practical applications, including privacy preserving data mining and location-based services. In this work, we develop a new approach for the PSI problem within the federated analytics framework. In particular, we consider a setting where a server wants to determine (query) which among its local set of data identifiers appears coupled with the same value in at least K of the N parties. Applications for this framework include but are not limited to: double-filing insurance verification, credit scoring and password checkup on an institutional level. To address the proposed setting, we propose a new protocol Fed-K-PSI that allows the server to answer this query while being oblivious to the data of identifiers that do not satisfy the distributed query at the parties. In addition, Fed-K-PSI also maintains the anonymity of the parties by hiding which K parties satisfied the query, or which value associated with the identifier which caused the query to be successful. Our proposed setting does not lend itself directly to state-of-the-art approaches in PSI based on Oblivious Transfer, since the server does not have a complete representation of a datapoint (only the identifier, but no value). Our proposed approach tackles this problem by constructing a distributed function at the parties, which encodes the datapoints and returns a deterministic known property if and only if the value for a given identifier is the same in at least K of the N parties. We show that Fed-K-PSI achieves a strong information-theoretic privacy guarantee and is resilient to collusion scenarios among honest-but-curious parties. We also evaluate Fed-K-PSI via extensive experiments to study the effect of the different system parameters.