Speaker: Dr. Satrajit Ghosh, IIT Kharagpur
Abstract: Private set intersection (PSI) is a special instance of secure multi-party computation (MPC). In PSI two (or more) mutually distrusting parties want to learn the intersection of their private sets. One can use generic techniques for MPC in order to accomplish this task, however it turns out that it is possible to achieve much better performance with special purpose protocols for PSI. Efficient PSI protocols have numerous applications in botnet detection, data mining, online advertising, private contact discovery, social networks, measuring ad-conversion rates, contact tracing and many more. Due to its applicability in practice, a long line of works have considered the problem in the two-party, the multi-party, and the server-aided setting with both passive and active security. In spite of huge amounts of work, actively secure, concretely efficient PSI protocols with optimal communication remain as an active area of research.
In CRYPTO 2019 we explored the possibility of further reducing the communication complexity of PSI protocols, which is impossible in general settings. However, for a variant of PSI, namely threshold PSI, it is indeed possible to achieve sub-linear communication under certain circumstances.
In this talk I will give a very brief overview of PSI and try to motivate the problem with some real-life applications. Later I’ll define threshold PSI and show how we achieve sub-linear threshold PSI protocol under certain assumptions.