Faster Private Set Intersection based on OT Extension (Full Version)
Benny Pinkas, Thomas H. Schneider, Michael Zohner · 2014
Private set intersection (PSI) allows two parties to com-pute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure com-putation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it difficult to identify the solution that performs best in a re-spective scenario, especially since they were not all im-plemented and compared in the same setting. In this work, we give an overview on existing PSI pro-tocols that are secure against semi-honest adversaries. We take advantage of the most recent efficiency improve-ments in OT extension to propose significant optimiza-tions to previous PSI protocols and to suggest a new PSI protocol whose runtime is superior to that of existing pro-tocols. We compare the performance of the protocols both theoretically and experimentally, by implementing all protocols on the same platform, and give recommen-dations on which protocol to use in a particular setting. 1