Secure Outsourced Private Set Intersection with Linear Complexity

In the context of privacy preserving protocols, Private Set Intersection (PSI) plays an important role due to their wide applications in recent research community. In general, PSI involves two participants to securely determine the intersection of their respective input sets, not beyond that. These days, in the context of PSI, it is become a common practice to store datasets in the cloud and delegate PSI computation to the cloud on outsourced datasets, similar to secure cloud computing. We call this outsourced PSI as OPSI. In this paper, we design a new construction of OPSI in malicious setting under the Decisional Diffie-Hellman (DDH) assumption without using any random oracle. In particular, our OPSI is the first that incurs linear complexity in malicious environment with not-interactive setup. Further, we employ a random permutation to extend our OPSI to its cardinality variant OPSI-CA. In this case, all the properties remain unchanged except that the adversarial model is semi-honest instead of malicious.