Structure-Aware Private Set Intersection, With Applications to Fuzzy Matching

ePrint Report: Structure-Aware Private Set Intersection, With Applications to Fuzzy Matching

Gayathri Garimella, Mike Rosulek, Jaspal Singh

In two-party private set intersection (PSI), Alice holds a set $X$, Bob holds a set $Y$, and they learn (only) the contents of $X \cap Y$.
We introduce structure-aware PSI protocols, which take advantage of situations where Alice's set $X$ is publicly known to have a certain structure.
The goal of structure-aware PSI is to have communication that scales with the description size …

applications eprint report private set intersection