TY - JOUR T1 - Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? JF - 19th Network and Distributed Security Symposium Y1 - 2011 A1 - Huang,Y. A1 - Evans,D. A1 - Katz, Jonathan AB - Cryptographic protocols for Private Set Intersection (PSI)are the basis for many important privacy-preserving ap- plications. Over the past few years, intensive research has been devoted to designing custom protocols for PSI based on homomorphic encryption and other public-key tech- niques, apparently due to the belief that solutions using generic approaches would be impractical. This paper ex- plores the validity of that belief. We develop three classes of protocols targeted to different set sizes and domains, all based on Yao’s generic garbled-circuit method. We then compare the performance of our protocols to the fastest custom PSI protocols in the literature. Our results show that a careful application of garbled circuits leads to solu- tions that can run on million-element sets on typical desk- tops, and that can be competitive with the fastest custom protocols. Moreover, generic protocols like ours can be used directly for performing more complex secure com- putations, something we demonstrate by adding a simple information-auditing mechanism to our PSI protocols. ER -