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.