Structure-Aware Private Set Intersection, With Applications to Fuzzy Matching
In regular PSI, we compute the intersection between two sets X and Y from Alice and Bob. In structure aware PSI, we assume that Alice's set X is publicly known to have a certain structure. The goal of structure-aware PSI is to have communication that scale with the description size of Alice's set rather than its cardinality.
Presents a generic compiler: If there exists a compact Function Secret Sharing (FSS) for a class of structured sets, then there exists a semi-honest 2-party PSI protocol whose communication cost is proportional only to the FSS share size.
Resources
- Github Implementation: https://github.com/osu-crypto/FuzzyPSI/tree/fuzzyPSI/cmake
References
Gayathri Garimella, Mike Rosulek, and Jaspal Singh. 2022. “Structure-Aware Private Set Intersection, With Applications to Fuzzy Matching.” https://eprint.iacr.org/2022/1011.