Peter Byerley rindal: Fast and Secure Private Set Intersection

Private Set Intersection (PSI) refers to the multi-party problem of identifying the common elements between two or more sets while hiding all other items. For example, identifying mutual friends without revealing all of the contacts to the other party. PSI has numerous applications including social networking, voter registration, web advertising, malware detection and many more. Over the last half decade, significant progress has been made towards practical two-party PSI protocols. This talk will present two of these improvements,  

1) A malicious secure PSI protocol (CCS'17) capable of intersecting two sets of one million items in 12 seconds.
2) The first PSI protocol (CCS'17) built from fully homomorphic encryption which achieves sublinear communication and fast running-times. 

The latter approach takes just 3 seconds & 12MB to intersect 5 thousand elements with 16 million elements and requires minimal computation by the party with the smaller set. Due to the asymmetry in set sizes, this protocol is extremely well suited for many mobile applications. Recently, Signal, the popular secure messaging app, has expressed interest in PSI techniques to allow the contacts of their users to automatically be added to the Signal app without Signal learning the user's contacts. Our PSI protocol based on fully homomorphic encryption offers the first practical solution without the need for strong trusted hardware assumptions.