Distance-Aware OT with Application to Fuzzy PSI

A two-party fuzzy private set intersection (PSI) protocol between Alice and Bob with input sets allows Alice to learn nothing more than the points of Bob that are “close’’ to its points in some metric space. Fuzzy PSI is a valuable privacy tool in scenarios where PSI needs to be computed over imprecise or measurement-based data, such as GPS coordinates or healthcare data. Previous approaches to fuzzy PSI rely on asymmetric cryptographic primitives, generic two-party computation techniques like garbled circuits, or function secret sharing methods, all of which are computationally intensive and lead to poor concrete efficiency.

This talk introduces a new modular framework for semi-honest fuzzy PSI, primarily built on efficient symmetric key primitives. The core idea is to reduce the design of fuzzy PSI to a novel variant of oblivious transfer (OT), which we term distance-aware random OT (daOT). We propose efficient constructions for daOT based on standard OT techniques tailored for small domains, supporting distance metrics such as the Chebyshev norm, the Euclidean norm, and the Manhattan norm.