Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?

TitlePrivate Set Intersection: Are Garbled Circuits Better than Custom Protocols?
Publication TypeJournal Articles
Year of Publication2011
AuthorsHuang Y, Evans D, Katz J
Journal19th Network and Distributed Security Symposium
Date Published2011///

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.