@article {15069,
	title = {Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?},
	journal = {19th Network and Distributed Security Symposium},
	year = {2011},
	month = {2011///},
	abstract = {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{\textquoteright}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.
},
	author = {Huang,Y. and Evans,D. and Katz, Jonathan}
}
