Talk by Daniel Noble: Private Set Intersection with Linear Communication from General Assumptions

Title: Private Set Intersection with Linear Communication from General Assumptions

Abstract: This work presents an improved hashing-based algorithm for Private Set Intersection (PSI) in the honest-but-curious setting. The protocol is generic, modular and provides both asymptotic and concrete efficiency improvements over existing PSI protocols. If each player has m elements, our scheme requires only O(m?) communication between the parties, where ? is a security parameter. Our protocol builds on the hashing-based PSI protocol of Pinkas et al. (USENIX 2014, USENIX 2015), but we replace one of the sub-protocols (handling the cuckoo “stash”) with a special-purpose PSI protocol that is optimized for comparing sets of unbalanced size. This brings the asymptotic communication complexity of the overall protocol down from ?(m?) to O(m?), and provides concrete performance improvements (10-15% reduction in communication costs) over Kolesnikov et al. (CCS 2016) under real-world parameter choices. Our protocol is simple, generic and benefits from the permutation-hashing  optimizations  of  Pinkas  et  al.  (USENIX  2015)  and  the Batched, Relaxed Oblivious Pseudo Random Functions of Kolesnikov et al. (CCS 2016).

Speaker: Daniel Noble, PhD Student at University of Pennsylvania