Multi-Party Private Set Intersection in Vertical Federated Learning

Vertical federated learning (VFL) is a privacy-preserving machine learning framework in which the training dataset is vertically partitioned and distributed over multiple parties, i.e., for each sample each party only possesses some attributes of it. In this paper we address the problem of computing private set intersection (PSI) in VLF, in which a private set denotes the data possessed by a party satisfying some distinguishing constraint. This problem actually asks how the parties jointly compute the common IDs of their private sets, which plays a key role in many learning tasks such as Decision Tree Learning. Currently all known PSI protocols, to our knowledge, either involve expensive cryptographic operations, or are designed for the two-party scenario originally which will leak privacy-sensitive information in multi-party scenario if applied to each pair of parties gradually. In this paper we propose a new multi-party PSI protocol in VFL, which can even handle the case that some parties drop out in the running of the protocol. Our protocol achieves the security that any coalition of corrupted parties, which number is less than a threshold, cannot learn any secret information of honest parties, thus realizing the goal of preserving the privacy of the involved parties. Moreover, it only relies on light cryptographic primitives (i.e. PRGs) and thus works more efficiently compared to the known protocols, especially when the sample number of dataset gets larger and larger. Our starting point to solve the PSI problem in VFL is to reduce it to computing the AND operation of multiple bit-vectors, each held by one party, which are used to identify parties' private sets in their data. Then our main technical contribution is to present an efficient protocol for summing up these vectors, called MulSUM, and then adapt it to a desired protocol, called MulAND, to compute the AND of these vectors, which result actually identifies the intersection of private sets of all (online) parties, thus accomplishing the PSI issue.