[Resource Topic] 2017/1064: An Algebraic Approach to Maliciously Secure Private Set Intersection

Welcome to the resource topic for 2017/1064

An Algebraic Approach to Maliciously Secure Private Set Intersection

Authors: Satrajit Ghosh, Tobias Nilges


Private set intersection is an important area of research and has been the focus of many works over the past decades. It describes the problem of finding an intersection between the input sets of at least two parties without revealing anything about the input sets apart from their intersection. In this paper, we present a new approach to compute the intersection between sets based on a primitive called Oblivious Linear Function Evaluation (OLE). On an abstract level, we use this primitive to efficiently add two polynomials in a randomized way while preserving the roots of the added polynomials. Setting the roots of the input polynomials to be the elements of the input sets, this directly yields an intersection protocol with optimal asymptotic communication complexity O(m\kappa). We highlight that the protocol is information-theoretically secure assuming OLE. We also present a natural generalization of the 2-party protocol for the fully malicious multi-party case. Our protocol does away with expensive (homomorphic) threshold encryption and zero-knowledge proofs. Instead, we use simple combinatorial techniques to ensure the security. As a result we get a UC-secure protocol with asymptotically optimal communication complexity O((n^2+nm)\kappa), where n is the number of parties, m is the set size and \kappa the security parameter. Apart from yielding an asymptotic improvement over previous works, our protocols are also conceptually simple and require only simple field arithmetic. Along the way we develop tools that might be of independent interest.

ePrint: https://eprint.iacr.org/2017/1064

Talk: https://www.youtube.com/watch?v=IYfCf1vD5_o

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .