SaTC: CORE: Small: New Approaches for Fuzzy Private Set Intersection

Oregon State University, Corvallis OR

Investigators

Abstract

In private set intersection (PSI), two parties each have a set of items and wish to learn which items they have in common, without revealing anything else about their sets. Current techniques for PSI are practical and scalable, but they require exact matches between the parties' items. This project introduces new techniques for "fuzzy PSI", where the parties learn which of their items are "close" according to some distance metric and threshold distance. Fuzzy PSI enables new privacy-enhancing applications on noisy real-world data sources. The project aims to develop practical fuzzy PSI protocols using two new approaches. The first involves novel connections to function secret sharing (FSS). Different distance metrics will be supported by developing new FSS constructions in the relevant geometry. Other newly identified properties of FSS schemes relate to performance and security properties of the fuzzy PSI protocol. The second fuzzy PSI approach involves locality sensitive hashing and a method of embedding protocol messages into polynomials. Taken together, the new techniques should significantly expand the kinds of privacy-enhancing analytics that can be done on noisy data, like biometric or geographical data. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.