Solving Private Set Intersection via Cuckoo Hashing - Benny Pinkas, Bar-Ilan University, Israel

Explore private set intersection (PSI) protocols and their applications in this comprehensive lecture. Learn about custom PSI protocols and their limitations, then delve into a novel approach using generic multi-party computation (MPC) protocols with Cuckoo hashing. Discover how this method achieves linear-time comparisons while addressing the challenge of minimizing failure probability. Gain insights into the applications of PSI in fields such as online advertising and understand the motivations behind using circuit-based protocols. Examine the technical aspects of sorting networks, error probability handling, and asymptotic complexity. Suitable for researchers interested in security and algorithms, this talk requires basic knowledge of cryptography and covers topics including naive PSI protocols, circuit-based approaches, and future research directions in the field.

A naive PSI protocol
Applications of PSI
Application: Online Advertising
Performance Classification (PSZ)
Motivation for using circuits
A circuit based protocol
A circuit comparing two s-bit values
Sorting networks
Handling the Error Probability
Asymptotic O(n) via Mirror Hashing
Better 2D Cuckoo variant
Circuit size
Contributions of the new protocol
Further Research Directions