Practical Third-Party Private Set Intersection Protocol from Homomorphic Encryption

As a special case of secure multi-party computing, private set intersection (PSI) protocol allows two parties to compute the intersection of their sets without revealing any information other than the intersection. We consider a variant of PSI, namely third-party PSI, which has important applications in scenarios such as advertising market and medical research. In the setting, a third-party Q with no input privately receives the intersection of the other two parties’ sets, while the two parties output nothing. We propose a general construction of third-party PSI protocol from leveled fully homomorphic encryption, which ensure privacy-preserving data intersection. The proposed construction can support intersection of arbitrary-length items by polynomial links, and its security can be proven in the presence of semi-honest adversaries. Compared with existing protocols, the instantiation of the proposed general construction achieves higher computational efficiency while maintaining the same communication complexity. More importantly, their protocol relies on the ideal permutation assumption, whereas the proposed protocol only utilizes practical leveled full homomorphic encryption and OT extension protocol, thus making it more valuable for practical use.