Set intersection protocol with privacy preservation

The Private Set Intersection Protocol (PSI) is one of the fundamental primitives of secure multi-party computations. This primitive allows several parties who do not trust each other to work together to calculate the intersection of their secret sets without disclosing additional information about these sets. This allows users to jointly analyze data without revealing confidential information to each other. This paper describes a new protocol for the intersection of private sets for 3 or more participants. The protocol works in a network with a “ring” type topology which minimizes the number of necessary communication channels between users. The protocol is based on the idea of conditional zero-sharing which allows using a secret sharing scheme to determine whether an element of the set belongs to all users or not. To evaluate the performance of the proposed solution, a software implementation of the protocol in C++ is proposed. The security of the developed protocol for three or more users is shown, provided that users do not conspire with each other for an “Honest-But-Curious” attacker model. Proposed model implies that the attacker is one of the protocol participants who performs the protocol correctly, but can analyse the information obtained during this process to gain benefits. The security of the protocol is based only on the assumption that the attacker lacks information to obtain any useful data from the messages received during the protocol execution. Thus, this protocol is information-theoretically secure. The presented protocol can be used for confidential data analysis, for example, when several companies exchange information about common customers. The protocol allows three users to find the intersection of sets of sizes 106 in about 42 s. In the present implementation, it is possible to add multithreading or transfer large matrix calculations from the processor to the GPU.