| 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’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.
|
