Date Added: Feb 2012
Cryptographic protocols for Private Set Intersection (PSI) are the basis for many important privacy-preserving applications. Over the past few years, intensive research has been devoted to designing custom protocols for PSI based on homomorphic encryption and other public-key techniques, apparently due to the belief that solutions using generic approaches would be impractical. This paper explores the validity of that belief. The authors develop three classes of protocols targeted to different set sizes and domains, all based on Yao's generic garbled-circuit method. They then compare the performance of their protocols to the fastest custom PSI protocols in the literature.