Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

Meng Hao, Xinpeng Yang, Hanxiao Chen, Tianwei Zhang, Haiyang Xue, Guomin Yang, Hongwei Li, Robert H. DengarXiv 2026 · arXiv

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:

  1. 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)$.
Figure 7: Fuzzy matching from role-reversed OPPRF.
  1. 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.
  2. 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.
  3. 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)$.
Figure 8: Comparison of fuzzy matching invocations of prior works (left) and ours (right) represented by gray shaded cells.

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

Abstract

In this paper, we present scalable fuzzy PSI protocols for general $L_{p \in [1, \infty]}$ distance, supporting both low- and high-dimensional sets. The core technique is two efficient fuzzy matching protocols. The first is built from a role-reversed oblivious PRF (OPRF) and realizes $O(d\log δ)$ overhead, compared to $O((\log δ)^d)$ in previous works. The second leverages customized oblivious transfer (OT) with $O(d\ell)$ overhead, where $\ell$ is the bit length of inputs, which is particularly suitable for short inputs. With these new techniques, we further propose a new dual-layer hashing framework for fuzzy PSI over low-dimensional sets, instantiated with our OT-based fuzzy matching and enhanced with a domain reduction optimization. The protocols achieve an overhead linear with $n, m, \log δ, 2^d$, without the $O((\log δ)^d)$ or $O(δ)$ factors present in prior works. {For high-dimensional sets, we construct fuzzy PSI protocols based on our OPRF- and OT-based fuzzy matching, which achieve an asymptotic overhead linear with $n, m, d$, and $\log δ$ but rely on the strong globally disjoint assumption.} Extensive evaluations demonstrate that our protocols achieve up to a $145\times$ speedup in running time and a $20\times$ reduction in communication cost compared to van Baarsen and Pu~(ASIACRYPT'25), and achieve up to a $25\times$ speedup in running time and up to a $17\times$ reduction in communication cost compared to Piske et al.~(CCS'25).
BibTeX
@misc{hao2026towards,
  author = {Meng Hao and Xinpeng Yang and Hanxiao Chen and Tianwei Zhang and Haiyang Xue and Guomin Yang and Hongwei Li and Robert H. Deng},
  title = {{Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching}},
  year = {2026},
  eprint = {2608.11526},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.11526},
}

Loading related content...

Figure