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

Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. There has been considerable research on designing custom secure protocols for computing PSI, due to the fact that PSI has many interesting applications and yet is not easily solvable by generic methods for secure multi-party computation (MPC). The drawback of these custom protocols is that they are tailored for solving the basic intersection problem and cannot be easily modified to computing other variants of it, which are often of great interest. Generic MPC protocols can be readily changed to compute arbitrary variants of the PSI problem, but are considerably less efficient. This talk will survey several custom PSI protocols. It will then describe how to apply generic MPC protocols to computing PSI while computing only a linear number of comparisons. The construction is based on a new variant of Cuckoo hashing. A major technical issue in the need for guaranteeing a failure probability that is much smaller than is often required for applications of hashing. Joint work with Thomas Schneider, Christian Weinert, Udi Wieder and Michael Zohner. This talk is suitable for researchers with an interest in security and algorithms, and requires a basic knowledge of cryptography. Biography Benny Pinkas is a member of the Department of Computer Science at Bar Ilan University, and deputy director of the BIU Center for Research in Applied Cryptography and Cyber Security. He has worked in the research labs of Intertrust Technologies, Hewlett-Packard, Google and VMware. His main research areas are cryptography, computer security and privacy, with a focus on secure computation. He received a starting grant from the ERC, as well as multiple other research grants. #TuringSeminars