Private set intersection (PSI) allows two parties, who each hold a set of
items, to compute the intersection of those sets without revealing anything
about other items. Recent advances in PSI have significantly improved its
performance for the case of semi-honest security, making semi-honest PSI a
practical alternative to insecure methods for computing intersections. However,
these protocols have two major drawbacks: 1) the amount of data
required to be communicated can be orders of magnitude larger than an insecure
solution and 2) when in the presence of malicious parties the security
of these protocols breaks down.
In this work, four malicious secure PSI protocols are introduced along with
three semi-honest protocols which have sublinear communication. These
protocols are based on a combination of fast symmetric-key primitives and
fully homomorphic encryption. Three of these protocols represent the current
state of the art for their respective settings.
The practicality of these protocols are demonstrated with prototype implementations.
To securely compute the intersection of two sets of size 2²⁰ in the malicious setting requires only 13 seconds, which is ~ 450x faster than the previous best malicious-secure protocol (De Cristofaro et al, Asiacrypt
2010), and only 3x slower than the best semi-honest protocol (Kolesnikov et
al., CCS 2016). Alternatively, when computing the intersection between set
sizes of 2¹⁰ and 2²⁸, our fastest protocol require just 6 seconds and 5MB of