TL;DR
This paper introduces highly scalable protocols for Fuzzy Private Set Intersection (PSI) across general $L_p$ distance metrics, accommodating both low- and high-dimensional data. By designing novel role-reversed oblivious PRF (OPRF) and customized oblivious transfer (OT) fuzzy matching techniques alongside a dual-layer hashing framework, the authors achieve up to a $145\times$ computational speedup and a $20\times$ reduction in communication overhead compared to state-of-the-art methods.
What Problem Does This Paper Address?
Traditional Private Set Intersection (PSI) allows two parties—a sender and a receiver—to find the exact common elements in their respective datasets without revealing anything else. However, real-world data like biometrics (fingerprints, iris scans) or GPS locations are inherently noisy, requiring approximate or fuzzy matching rather than exact string equality.
Fuzzy PSI solves this by identifying items that fall within a specified distance threshold ($\delta$). Unfortunately, existing fuzzy PSI protocols suffer from severe efficiency bottlenecks: they either rely on heavy, computation-expensive cryptographic primitives (like Additively Homomorphic Encryption or Garbled Circuits) or exhibit poor asymptotic complexity that scales exponentially with the data's dimensionality ($d$) or poorly with large distance thresholds ($\delta$). This paper aims to bridge the gap, providing concrete and asymptotic efficiency guarantees for both low- and high-dimensional settings.
Methods
The authors propose two main single-point fuzzy matching protocols and compile them into multi-point fuzzy PSI frameworks:
- Role-Reversed Oblivious PRF (OPRF): Prior OPRF-based approaches required the receiver to compute an exponential combination of PRF evaluations to check multi-dimensional intervals, leading to a massive $O((\log \delta)^{d/2})$ computational bottleneck. The authors elegantly solve this by introducing a second, role-reversed OPPRF invocation to compress these evaluations into a single value before performing a Private Equality Test (PEQT). This drops the computational overhead to a clean $O(d \log \delta)$.
- Customized Oblivious Transfer (OT): For short inputs, they design an OT-based protocol that avoids the statistical security parameter ($\lambda$) overhead entirely, achieving $O(d\ell)$ complexity where $\ell$ is the bit length.
- Dual-Layer Hashing Framework: For low-dimensional sets, they combine spatial hashing with Cuckoo hashing. Instead of forcing the protocol to execute $O(2^d n)$ heavy fuzzy matching operations across all receiver search cells, they filter the candidate space down to roughly $m$ pairs (matching the sender's points), drastically reducing the number of cryptographic invocations.
- Domain Reduction Optimization: They introduce a shift-and-truncate operation to map points into a much smaller, localized coordinate space, optimizing the OT-based matching phase.
Datasets
The evaluation uses synthetic datasets specifically generated to control parameters like set size ($m, n \in \{2^{12}, 2^{16}, 2^{18}\}$), dimension ($d$ ranging from 2 to 8 for low-dimensional, and 16 to 64 for high-dimensional), and distance thresholds ($\delta \in \{16, 64, 256, 1024\}$). This is standard practice in PSI research to rigorously benchmark concrete performance across varying scale and noise levels.
Key Insights and Ideas
- The Role-Reversal Trick: Flipping the client-server roles in a second OPPRF round allows the parties to securely compress intermediate multi-dimensional interval checks into a single value. This bypasses the combinatorial explosion that plagued prior trie-based fuzzy matching schemes.
- Filtering the Empty Space: In spatial hashing, the receiver typically checks all $2^d$ neighboring grid cells for every single point. The authors realized that the vast majority of these cells are empty on the sender's side. By using Cuckoo hashing to align only the cells that actually contain sender points, they cut down the number of heavy fuzzy matching invocations from $O(2^d n)$ to $O(m)$.
Key Results
- Low-Dimensional Sets: Under $L_\infty, L_1,$ and $L_2$ distances, the proposed protocol achieves up to a $145\times$ speedup in execution time and a $20\times$ reduction in communication cost compared to van Baarsen and Pu (ASIACRYPT'25). Compared to Piske et al. (CCS'25), it yields up to a $25\times$ speedup and a $17\times$ reduction in communication.
- High-Dimensional Sets: For dimensions ranging from 16 to 64, the protocols demonstrate up to a $36\times$ reduction in running time and up to a $54\times$ lower communication cost compared to the state-of-the-art OPRF baseline.
Limitations and Future Work
- The Curse of High Dimensions: For high-dimensional datasets ($d \ge 16$), the protocol relies on a strict globally disjoint assumption (meaning the projections of the datasets' bounding balls do not overlap in any single dimension). The authors openly acknowledge that this structural constraint is strong and not entirely realistic for arbitrary real-world distributions.
- Low-Dimensional Exponential Factor: The low-dimensional framework still retains an exponential factor of $2^d$ due to its reliance on spatial grid partitioning, making it impractical for moderately high dimensions without the globally disjoint assumption.
- Future Work: Extending the OPRF-based protocol to support general $L_p$ distances (beyond $L_\infty$) with the same logarithmic asymptotic overhead remains an open challenge.
Summary updated