Traditional private set intersection (PSI) involves a receiver and a sender holding sets X and Y, respectively, with the receiver learning only the intersection X∩Y. We turn our attention to its fuzzy variant, where the receiver holds |X| hyperballs of radius δ in a metric space and the sender has |Y| points. Representing the hyperballs by their center, the receiver learns the points (formula presented) for which there exists (formula presented) with respect to some distance metric. Previous approaches either require general-purpose multi-party computation (MPC) techniques like garbled circuits or fully homomorphic encryption (FHE), leak details about the sender’s precise inputs, support limited distance metrics, or scale poorly with the hyperballs’ volume. This work presents the first black-box construction for fuzzy PSI (including other variants such as PSI cardinality, labeled PSI, and circuit PSI), which can handle polynomially large radius and dimension (i.e., a potentially exponentially large volume) in two interaction messages, supporting general (formula presented) distance, without relying on garbled circuits or FHE. The protocol excels in both asymptotic and concrete efficiency compared to existing works. For security, we solely rely on the assumption that the Decisional Diffie-Hellman (DDH) holds in the random oracle model.

doi.org/10.1007/978-3-031-58740-5_12
Lecture Notes in Computer Science
Secure scalable policy-enforced distributed data processing
43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques: EUROCRYPT 2024

van Baarsen, A., & Köhne, A. (2024). Fuzzy Private Set Intersection with large hyperballs. In Advances in Cryptology - EUROCRYPT 2024 (pp. 340–369). doi:10.1007/978-3-031-58740-5_12