Private set intersection from homomorphic encryption

Abstract

Secure Multiparty Computation (MPC) is a broad area that allows some parties to jointly compute a function without revealing their private inputs. Private Set Intersection (PSI) is an important problem in MPC, where two set holders want to learn the intersection of their sets while not leaking other information. The asymmetric case of the PSI problem has seen practical application in private database querying, biometric authentication, or private contact discovery. In the past few years, there have been new approaches in asymmetric PSI to take advantage of the receiver’s small set size to improve computation and communication efficiency in their protocol. This work aims to provide an implementation for the new Branching Program approach, as well as compare it with previous methods. In this paper, a new attempt to provide malicious security in asymmetric PSI while keeping communication dependent only on the receiver’s set size is also reported.