Applications of Secure Computation to Set Intersection



Journal Title

Journal ISSN

Volume Title



Secure multi-party computation protocols allow many parties to compute a function over their private data without revealing their data to other parties. We look at a concrete example of secure multi-party computation in real world applications: private set intersection (PSI). We design more efficient private set intersection protocols with different flavors: two-party PSI with an untrusted third party, two-party asymmetric PSI via vector OLE, and PSI via MPC-in-the-head. Our PSI protocols are designed to meet different needs. The PSI via MPC-in-the-head protocols allow two or more parties to compute the intersection between their input sets, and the output is learned by all the parties. The other two focus on the two-party setting with a clear use case for each. The PSI via vector OLE protocols focus on the problem of mobile contact discovery. They are executed in two-party setting between a server that has a large input set (billions of items) and a client with much smaller input set (a few thousand items). The two-party PSI with an untrusted third party protocols allow the two parties, which provide input, to securely compute an arbitrary function over the intersection.