An algebraic approach to maliciously secure private set intersection

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Private set intersection (PSI) 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κ). We highlight that the protocol is information-theoretically secure against a malicious adversary 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((n2+nm)κ), where n is the number of parties, m is the set size and κ is 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 techniques that might be of independent interest.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2019 : 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsYuval Ishai, Vincent Rijmen
Number of pages32
PublisherSpringer VS
Publication year2019
Pages154-185
ISBN (print)9783030176587
DOIs
Publication statusPublished - 2019
Event38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany
Duration: 19 May 201923 May 2019

Conference

Conference38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
LandGermany
ByDarmstadt
Periode19/05/201923/05/2019
SeriesLecture Notes in Computer Science
Volume11478
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 176198398