Keeping your Friends Secret: Improving Private Set Intersection

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, we introduce new PSI protocols that are secure in the presence of malicious adversaries and other protocols which are semi-honest secure and have sublinear communication. Our protocols are based on a combination of fast symmetric-key primitives and fully homomorphic encryption.

We demonstrate our protocols' practicality with a prototype implementations. To securely compute the intersection of two sets of size 2^20 in the malicious setting requires only 13 seconds, which is ~450x faster than the previous best malicious-secure protocol, and only 3x slower than the best semi-honest protocol. Alternatively, when computing the intersection between set sizes of 2^10 and 2^28, our fastest protocol require just 6 seconds and 5MB of communication.

Major Advisor: Mike Rosulek
Committee: Rakesh Bobba
Committee: Atilla Yavuz
Committee: Payman Mohassel
GCR: Clayton Petsche