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

在私有集合交集（PSI）中，两方都有一个项目集合，并希望了解他们有哪些共同的项目，而不透露关于他们集合的任何其他信息。目前的PSI技术是实用的和可扩展的，但它们需要双方的项目之间的精确匹配。这个项目引入了新的技术，“模糊PSI”，其中各方了解他们的项目是“接近”根据一些距离度量和阈值距离。模糊PSI使新的隐私增强的应用程序在嘈杂的现实世界的数据源。该项目旨在开发实用的模糊PSI协议使用两种新的方法。第一个涉及到函数秘密共享（FSS）的新连接。不同的距离度量将通过在相关几何结构中开发新的FSS结构来支持。其他新确定的FSS方案的属性涉及到模糊PSI协议的性能和安全属性。第二种模糊PSI方法涉及局部敏感散列和将协议消息嵌入多项式的方法。总的来说，这些新技术应该会大大扩展可以对生物特征或地理数据等噪声数据进行的隐私增强分析的种类。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

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.