Paper 2023/1166

Malicious Secure, Structure-Aware Private Set Intersection

Gayathri Garimella, Oregon State University
Mike Rosulek, Oregon State University
Jaspal Singh, Oregon State University

Structure-Aware private set intersection (sa-PSI) is a variant of PSI where Alice's input set $A$ has some publicly known structure, Bob's input $B$ is an unstructured set of points, and Alice learns the intersection $A \cap B$. sa-PSI was recently introduced by Garimella et al. (Crypto 2022), who described a semi-honest protocol with communication that scales with the description size of Alice's set, instead of its cardinality. In this paper, we present the first sa-PSI protocol secure against malicious adversaries. sa-PSI protocols are built from function secret sharing (FSS) schemes, and the main challenge in our work is ensuring that multiple FSS sharings encode the same structured set. We do so using a cut-and-choose approach. In order to make FSS compatible with cut-and-choose, we introduce a new variant of function secret sharing, called derandomizable FSS (dFSS). We show how to construct dFSS for union of geometric balls, leading to a malicious-secure sa-PSI protocol where Alice's input is a union of balls. We also improve prior FSS constructions, giving asymptotic improvements to semi-honest sa-PSI.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2023
secure computationprivate set intersectionfunction secret sharing
Contact author(s)
garimelg @ oregonstate edu
rosulekm @ eecs oregonstate edu
singjasp @ oregonstate edu
2023-07-30: approved
2023-07-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gayathri Garimella and Mike Rosulek and Jaspal Singh},
      title = {Malicious Secure, Structure-Aware Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1166},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.