Paper 2026/262

Fuzzy Private Set Intersection under Density-Bounded Assumptions

Abstract

This paper presents a new fuzzy private set intersection (FPSI) protocol, a two-party protocol to securely identify similar items across private sets. Our design departs from the prevailing separation-based paradigm---e.g., ``apart by $2\delta$'' or the disjoint projection assumption---which either incurs exponential overhead in dimensionality or requires high dimensionality to justify the assumption. Instead, we address this tension by explicitly allowing collisions within $\delta$-balls, but requiring that their multiplicity be bounded per axis. We formalize this new structural property as $C$-max collision. We theoretically analyze its plausibility on several common distributions, e.g., the uniform distribution, and real datasets, and provide an efficient algorithm to verify this assumption. Under the $C$-max collision property, we propose an efficient FPSI protocol for $\ell_{\infty}$ distance that supports both low- and high-dimensional regimes. Our construction is based on a novel abstraction that views FPSI as an oblivious intersection of membership tags, which natively handles axis-wise matching multiplicity. We capture its requirements through a new functionality called oblivious selected set intersection, along with its instantiation based on symmetric key techniques. Assuming the $C$-max collision property on the receiver's set, our protocol achieves computation/communication complexities scaling linearly with both parties' set sizes for a fixed $C$. We implement our protocol and conduct extensive evaluation. While a direct comparison is infeasible, ours achieves online efficiency comparable to state-of-the-art separation-based FPSI protocols in both low- and high-dimensional regimes.

Note: This is the camera-ready version that will appear at IEEE S&P 2027.