Abstract. In this presentation, we talk about a new Approximate Private Set Intersection scheme that allows for fuzzy matching of set items. Under the assumption that the set elements are either close (due to errors or rounding) or far enough apart, we can greatly improve the performance of matching close elements under various distance metrics. Asymptotically, we improve the result from quadratic to near-linear, and empirically is 20x faster with 30% less communication than previous schemes. This adds to the growing menagerie of PSI flavors, and in this talk we also explore broad and narrow approaches towards a path to standardizing specific PSI schemes or PSI as a whole.
Joint work with: Wutichai Chongchitmate, and Rafail Ostrovsky
WPEC 2024: NIST Workshop on Privacy-Enhancing Cryptography 2024. Virtual, 2024-Sep-24–26.
NIST Workshop on Privacy-Enhancing Cryptography 2024
Starts: September 24, 2024Virtual
Security and Privacy: cryptography