%0 Journal Article %J 19th Network and Distributed Security Symposium %D 2011 %T Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? %A Huang,Y. %A Evans,D. %A Katz, Jonathan %X 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. %B 19th Network and Distributed Security Symposium %8 2011/// %G eng