Efficient and Malicious Secure Three-Party Private Set Intersection Computation Protocols for Small Sets

Private set intersection (PSI) allows participants who hold private sets to securely obtain the set intersection without revealing information about any elements other than the intersection. Most of the existing two-party/multi-party PSI protocols are based on the oblivious transfer (OT) protocol, which not only has high efficiency, but also brings huge cost of communication. However, expanding network bandwidth is very expensive or even infeasible in many scenarios, and there are few computationally efficient multi-party PSI protocols that do not rely on OT protocols. In this paper, three-party private set intersection computing protocols are constructed based on one round key agreement. The protocols are proved secure assuming the collusion attack of any two parties in the semi-honest model and malicious model, respectively. Through experimental simulation, in the large set scenario, compared with the existing OT-based multi-party PSI protocol, the three-party private set intersection computation protocols have the optimal number of communication rounds, and the amounts of communication is reduced by 89%~98%. In small set scenarios (500 items or less), compared with similar PSI protocols for weak communication networks, the protocols in our paper have optimal runtime and communication load, especially, and they get 10~25 times faster than PSI protocol relying on homomorphic encryption.