Paper 2025/911

Fuzzy Private Set Intersection from VOLE

Abstract

Private set intersection (PSI) is a well-researched cryptographic primitive that allows two parties to compute the intersection of their input sets without revealing any information about items outside of the intersection. Fuzzy private set intersection is a relatively new variant of PSI, where items are not matched exactly but ``fuzzily''. Most commonly, items are points $\mathbf{q},\mathbf{w}$ in $d$-dimensional integer space $\mathbb{Z}^d$ and a point is a fuzzy match to another if it lies within a ball of radius $\delta$ centered at this point, with respect to some distance metric. Previous works either only support infinity $(L_{\infty}$) distance metric and standard PSI functionality, or support general Minkowski ($L_{\mathsf{p}}$, $\mathsf{p}\in[1,\infty]$) distance metrics and realize richer functionalities but rely on expensive homomorphic encryptions. Our work aims to bridge this gap by giving the first construction of a fuzzy PSI protocol for general Minkowski distance metrics relying on significantly cheaper operations during the online phase. Our main building block is a novel fuzzy matching protocol based on an oblivious pseudorandom function (OPRF), which can be realized very efficiently from vector oblivious linear evaluation (VOLE). Our protocol is able to preserve the asymptotic complexity as well as the simplicity of the fuzzy matching protocol from van Baarsen and Pu (Eurocrypt '24), while being much more concretely efficient. Additionally, we achieve several asymptotic improvements by representing intervals succinctly. Finally, we present the first fuzzy PSI protocol for infinity distance that places no assumptions on the sets of points, while maintaining asymptotic complexities comparable to the state-of-the-art fuzzy PSI protocol.

Note: Added some details on how the protocol in Section 11.1 can deal with overlapping prefixes on all dimensions by using weak labeled PSI supporting variable-size labels.