[Resource Topic] 2023/1166: Malicious Secure, Structure-Aware Private Set Intersection

Welcome to the resource topic for 2023/1166

Malicious Secure, Structure-Aware Private Set Intersection

Authors: Gayathri Garimella, Mike Rosulek, Jaspal Singh


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.

ePrint: https://eprint.iacr.org/2023/1166

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 .