Private set intersection (PSI) allows two parties to compute 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 computation 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 respective scenario, especially since they were not compared in the same setting. In addition, existing PSI protocols are several orders of magnitude slower than an insecure naïve hashing solution, which is used in practice. In this article, we review the progress made on PSI protocols and give an overview of existing protocols in various security models. We then focus on PSI protocols that are secure against semi-honest adversaries and take advantage of the most recent efficiency improvements in Oblivious Transfer (OT) extension, propose significant optimizations to previous PSI protocols, and suggest a new PSI protocol whose runtime is superior to that of existing protocols. We compare the performance of the protocols, both theoretically and experimentally, by implementing all protocols on the same platform, give recommendations on which protocol to use in a particular setting, and evaluate the progress on PSI protocols by comparing them to the currently employed insecure naïve hashing protocol. We demonstrate the feasibility of our new PSI protocol by processing two sets with a billion elements each. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.  Private set intersection (PSI) allows two parties, P 1 and P 2 , holding sets X and Y , respectively, to identify the intersection X ∩ Y without revealing any information about elements that are not in the intersection. The basic PSI functionality can be used in applications where two parties want to perform JOIN operations over database tables that they must keep private, e.g., private lists of preferences, properties, or personal records of clients or patients. PSI was used in several research projects for privacy-preserving computation of functionalities such as relationship path discovery in social networks (Mezzour et al. 2009 ), botnet detection (Nagaraja et al. 2010) , testing of fully sequenced human genomes (Baldi et al. 2011 ), proximity testing (Narayanan et al. 2011, or cheater detection in online games (Bursztein et al. 2011) . PSI has been a very active research field, and there have been many suggestions for PSI protocols. The large number of proposed protocols makes it non-trivial to perform comprehensive cross-evaluations. This is further complicated by the fact that many protocol designs have not been implemented and evaluated, were analyzed under different assumptions and observations, and were often optimized w.r.t. overall run-time while neglecting other relevant factors such as communication. Furthermore, even though several PSI protocols have been introduced, practical applications that need to compute the intersection of privacy-sensitive lists often use insecure solutions. The reason for the poor acceptance of secure solutions is, among others, the poor efficiency of existing schemes, which have more than two orders of magnitude more overhead than insecure solutions. In this article, we give an overview on existing efficient PSI protocols, optimize exiting PSI protocols, and describe a new PSI protocol based on efficient oblivious transfer (OT) extensions. We compare both the theoretical and empirical performance of all protocols on the same platform and evaluate their cost compared to the insecure hash-based solution used in practice. We show that our new PSI protocol achieves a reasonable overhead compared to solutions used in practice.
Existing PSI protocols are compared in REF , where experiments are performed for both equal and unequal number of inputs.
Scalable Private Set Intersection Based on OT Extension
TOPS
Computer Science