💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

This paper introduces the first concretely efficient fuzzy private set intersection protocols for general $L_p$ distances under one-sided assumptions, leveraging lightweight symmetric-key primitives and prefix trie techniques to achieve $O(\log \delta)$ complexity and significantly outperforming prior state-of-the-art works in both computation speed and communication overhead.

Original authors: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

Published 2026-08-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital age, two organizations often need to find common ground without revealing their entire secrets to one another. Imagine a hospital holding a list of patients with a specific condition and a research institute holding a list of volunteers. They want to know which volunteers are also patients, but neither side wants to hand over their full list, as that would expose private data about everyone else on the roster. Standard computer protocols can solve this exact matching problem efficiently, but they fail when the data is slightly messy. In the real world, names are misspelled, locations are slightly off, and biometric scans vary from day to day. If the hospital's record says "John Smith" and the volunteer's record says "Jon Smyth," a standard system sees no match, even though they are the same person. This is where "fuzzy" matching comes in, a method designed to find these approximate connections. However, doing this securely is incredibly difficult. If the system tries to compare every possible variation of every name against every other variation, the amount of data exchanged becomes so massive that the process grinds to a halt, or it requires such heavy mathematical machinery that it becomes impractical for everyday use.

A team of researchers has now developed a new way to perform this fuzzy matching that is both fast and lightweight. Their work focuses on a scenario where only one of the two parties needs to follow strict rules about how their data is arranged, while the other party can have data in any chaotic order. Previous attempts to solve this problem under such relaxed conditions relied on heavy, slow cryptographic tools or required both parties to have perfectly organized data, which is rarely the case in reality. The new method, created by Xinpeng Yang and colleagues from institutions in Singapore and the United States, achieves the same goal using only simple, fast building blocks. They managed to cut the time and data required for these comparisons by massive margins, making secure, approximate matching feasible for the first time in many real-world settings.

The core of the achievement lies in how the researchers handle the "distance" between data points. In this context, distance is a measure of how different two pieces of information are, such as how many letters differ between two names or how far apart two GPS coordinates are. The goal is to find pairs where this distance is smaller than a specific threshold. The researchers realized that previous methods tried to check every possible variation of a data point, which created a search space that grew explosively as the allowed difference increased. To fix this, they introduced a technique that acts like a smart filter. Instead of checking every single possibility, the system organizes the data into a tree-like structure that allows it to skip over huge chunks of irrelevant information instantly. This change reduced the computational effort from a level that grew exponentially with the size of the search to a level that grows only logarithmically. In practical terms, this means that even if the allowed difference between data points is doubled or tripled, the time it takes to run the check barely increases.

The team tested their new protocols against the best existing methods currently available. The results were dramatic. When compared to a recent protocol from 2024, their new system ran up to 239 times faster and used up to 20 times less communication bandwidth. Against a 2025 method, the speedup reached 518 times, with a 63-fold reduction in data transfer. In one specific comparison against another 2025 construction, the new system was nearly 5,000 times faster and required 282 times less communication. These numbers were not just theoretical; the researchers implemented the full system and ran extensive experiments across a wide range of data sizes and settings. They confirmed that their approach works whether the sender or the receiver is the one with the organized data, and it supports various types of distance measurements, not just simple ones.

A key innovation in their work was the ability to handle "one-sided" assumptions. In many previous secure systems, both parties had to agree to strict rules, such as ensuring their data points were spaced far enough apart to avoid confusion. This is often impossible in real life, where data arrives in clusters or random patterns. The new method only requires one side to have a somewhat organized dataset, while the other side can have completely arbitrary, messy data. This flexibility makes the technology applicable to scenarios like contact tracing or location-based services, where one entity might have a structured database of known locations while the other has a stream of unstructured user inputs. By relying solely on lightweight, symmetric-key techniques—essentially standard encryption tools that are fast and efficient—the researchers avoided the heavy, slow mathematical operations that had previously bogged down similar efforts.

The researchers also explored how to make the system even more efficient when the data is sparse, meaning the points are spread out rather than clustered. In these cases, they found that swapping the roles of the two parties in the matching process could further balance the workload and improve performance. This adaptability suggests the system can be tuned for different types of applications without needing a complete redesign. The work demonstrates that it is possible to build secure, privacy-preserving systems that are not only theoretically sound but also practically fast enough for real-world deployment.

The implications of this work extend beyond just speed. By making fuzzy matching efficient, the researchers have opened the door for more sophisticated privacy-preserving applications. Organizations that have long avoided sharing data because they feared privacy leaks or because the matching process was too slow can now consider secure collaboration. Whether it is matching patient records for medical research, verifying user identities without exposing biometric templates, or finding similar items in large catalogs without revealing the catalog contents, the barrier to entry has been significantly lowered. The study proves that with the right algorithmic approach, the trade-off between privacy and performance can be resolved, allowing data to flow securely even when it is imperfect or noisy.

In the end, the paper presents a concrete solution to a problem that has lingered for years: how to find approximate matches in private data without sacrificing speed or requiring unrealistic conditions. The researchers did not just propose a new idea; they built it, tested it, and showed that it outperforms everything that came before it by orders of magnitude. Their work stands as a testament to the power of refining the underlying logic of a problem rather than just trying to throw more computing power at it. For the curious observer, the result is a system that feels less like a heavy, clunky machine and more like a precise, efficient tool, ready to be used in the messy, imperfect world of real data.

Technical Summary: Efficient Fuzzy PSI under One-Sided Assumptions

Problem Statement

Fuzzy Private Set Intersection (PSI) enables two parties, a sender and a receiver, to identify elements in their respective input sets that are approximately matching. Specifically, given a distance threshold $\delta$ and a metric $dist(\cdot, \cdot)$ , the receiver learns all sender elements $\mathbf{q}$ for which there exists a receiver element $\mathbf{w}$ such that $dist(\mathbf{q}, \mathbf{w}) \le \delta$ .

While standard PSI has seen significant progress, fuzzy PSI faces a trade-off between efficiency and the strength of underlying assumptions. Existing constructions for general $L_p$ ( $p \in [1, \infty]$ ) distances typically fall into two categories:

Two-sided assumptions: Protocols requiring both parties' inputs to satisfy strong geometric separation (e.g., points are pairwise separated by $2\delta$ or $4\delta$ ). These are efficient but often unrealistic for real-world noisy data.
One-sided assumptions: Protocols where only one party's inputs must satisfy separation constraints, allowing the other party to hold arbitrary inputs. However, existing one-sided solutions either rely on heavyweight cryptographic primitives (e.g., Additively Homomorphic Encryption) or incur substantial asymptotic overhead in the threshold $\delta$ (e.g., $O(\delta)$ or $O((\log \delta)^d)$ ).

The core challenge addressed is constructing concretely efficient fuzzy PSI protocols for general $L_p$ distances under weak one-sided assumptions, relying solely on lightweight symmetric-key primitives.

Methodology

The authors propose a framework built on Secret-Shared Oblivious Programmable Pseudorandom Functions (so-OPPRF) and Spatial Hashing, enhanced by Prefix Trie techniques.

1. Multi-Point Fuzzy Matching Primitives

To handle arbitrary inputs from one party without leakage, the paper introduces two assumption-free multi-point fuzzy matching protocols:

1-to- $n$ Matching (Receiver holds arbitrary points): The sender programs a so-OPPRF with intervals around its single point. To prevent the receiver from inferring the sender's input distribution via collisions in aggregated shares (a leakage issue in prior work), the authors introduce Equality-conditional Randomization (EqRand). This primitive re-randomizes secret shares for non-matching inputs while preserving the correct sum for matching inputs, ensuring privacy even when multiple receiver points map to the same programmed interval.
$m$ -to-1 Matching (Sender holds arbitrary points): The roles are reversed. The receiver programs the so-OPPRF with intervals around its single point. The sender evaluates the function on its multiple points. Since the receiver does not reconstruct aggregated values from the sender's side, the leakage issue is avoided naturally, and no EqRand is required.

2. Fuzzy PSI under One-Sided Assumptions

Building on the primitives above, the authors construct full $m$ -to- $n$ fuzzy PSI protocols under two specific one-sided assumptions:

Unique Cell Assumption: Each spatial cell (of side length $2\delta$ ) contains at most one point from the constrained party.
Unique Block Assumption (Sparser): Each spatial cell intersects with at most one $L_\infty$ ball of the constrained party.

The protocol utilizes spatial hashing to partition the space. The constrained party programs the so-OPPRF with keys derived from their points and cell identifiers, ensuring collision-freedom. The unconstrained party evaluates the function on their points and neighboring cells. The use of so-OPPRF ensures that outputs are secret-shared, preventing either party from learning the other's raw data.

3. Prefix Trie Optimization

To address the linear or superlinear complexity scaling with $\delta$ found in prior works, the authors incorporate Prefix Trie techniques.

Mechanism: Instead of enumerating all points in an interval $[w - \delta, w + \delta]$ (which takes $O(\delta)$ ), the interval is encoded into $O(\log \delta)$ prefix nodes using the PxTrie algorithm.
Dimension-by-Dimension Filtering: Prior works required evaluating all combinations of prefixes across $d$ dimensions, leading to $O((\log \delta)^d)$ complexity. The authors introduce a Conditional Selection (ConSel) primitive that filters prefixes dimension-by-dimension. Since at most one prefix per dimension can match the target, the search space is pruned from $O((\log \delta)^d)$ to $O(d \cdot \log \delta)$ .
Result: This achieves $O(\log \delta)$ complexity in the threshold $\delta$ for general $L_p$ distances, a significant improvement over previous $O((\log \delta)^d)$ or $O(\delta)$ bounds.

4. Handling General $L_p$ Distances

For $L_p$ distances ( $p > 1$ ), the protocol encodes the $p$ -th power of the per-dimension distance contribution ( $|t|^p$ ) into the so-OPPRF values. The parties then perform secure multi-party computation (addition and multiplication) to aggregate these shares and check if the total distance is within the threshold $\delta^p$ .

Key Contributions

First Efficient One-Sided Fuzzy PSI for General $L_p$ : The paper presents the first concretely efficient protocols for general $L_p \in [1, \infty]$ distances under one-sided assumptions, relying exclusively on symmetric-key primitives (so-OPPRF, OKVS, silent OT).
Logarithmic Complexity in $\delta$ : By non-trivially integrating prefix trie techniques with a dimension-by-dimension filtering mechanism, the protocols achieve $O(\log \delta)$ complexity in the distance threshold, improving upon the $O((\log \delta)^d)$ or $O(\delta)$ complexities of state-of-the-art works.
Flexible Assumption Support: The framework supports both Sender-sided and Receiver-sided settings, as well as Unique Cell and Unique Block assumptions. The Unique Block assumption allows for further optimizations by reversing the roles of programming and evaluation to exploit the lower cost of programming vs. evaluating so-OPPRF.
Extensive Evaluation: The authors implemented the protocols and compared them against state-of-the-art works (van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6], etc.).

Experimental Results

The evaluation was conducted on a server with an AMD EPYC 9554 processor. The results demonstrate significant improvements in both communication and computation:

Against van Baarsen and Pu (EUROCRYPT'24): Up to 239 $\times$ faster computation and up to 20 $\times$ lower communication.
Against Dang et al. (CCS'25): Up to 518 $\times$ speedup and 63 $\times$ communication reduction.
Against Bui et al. (ASIACRYPT'25): Up to 4818 $\times$ faster computation and up to 282 $\times$ lower communication.

The prefix-optimized variants (Ours-Px) show superior performance in communication for large $\delta$ and high dimensions, while the non-optimized variants (Ours) are highly competitive for smaller thresholds due to lower computational overhead.

Significance and Claims

The paper claims to resolve the long-standing trade-off between the strength of geometric assumptions and the efficiency of fuzzy PSI protocols. By demonstrating that general $L_p$ fuzzy PSI can be achieved under weak one-sided assumptions using only lightweight symmetric-key primitives, the work makes fuzzy PSI more applicable to real-world scenarios where data is noisy and strict separation assumptions cannot be guaranteed.

The authors emphasize that their protocols significantly outperform prior works under comparable assumptions, achieving orders of magnitude improvements in efficiency. The introduction of the dimension-by-dimension filtering mechanism via prefix tries is highlighted as a key technical innovation that breaks the exponential dependency on dimensionality in the threshold parameter, making the protocols scalable for high-dimensional data and large matching thresholds.