International Association for Cryptologic Research

International Association
for Cryptologic Research


Malicious Secure, Structure-Aware Private Set Intersection

Gayathri Garimella , Oregon State University
Mike Rosulek , Oregon State University
Jaspal Singh , Oregon State University
DOI: 10.1007/978-3-031-38557-5_19 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Structure-Aware PSI (saPSI) is a variant of PSI where Alice's input set $A$ has some publicly known structure and Bob's input $B$ is an unstructured set of points and Alice wants to learn the intersection $A \cap B$. It was recently introduced by Garimella et al. (Crypto 2022); they present a semi-honest saPSI protocol with communication that scales with the description size of Alice's set, instead of its cardinality. In this paper, we present the first saPSI protocol secure against malicious-adversaries. We use a cut-and-choose approach to ensure that Alice uses valid FSS sharings, of the same underlying object. In order to handle a technical issue that arises, we introduce a new variant of function secret sharing, called derandomizable FSS (dFSS). We show how to extend prior FSS constructions for union of geometric balls, to meet the requirements of dFSS. Additionally, we improve FSS constructions that result in asymptotic improvements to the prior semi-honest structure-aware PSI protocol.
  title={Malicious Secure, Structure-Aware Private Set Intersection},
  author={Gayathri Garimella and Mike Rosulek and Jaspal Singh},