💻 computer science

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

This paper introduces scalable fuzzy Private Set Intersection (PSI) protocols for general $L_p$ distances in both low- and high-dimensional settings by leveraging efficient OPRF- and OT-based fuzzy matching techniques and a novel dual-layer hashing framework, achieving significant improvements in speed and communication costs compared to prior state-of-the-art works.

Original authors: Meng Hao, Xinpeng Yang, Hanxiao Chen, Tianwei Zhang, Haiyang Xue, Guomin Yang, Hongwei Li, Robert H. Deng

Published 2026-08-13

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Meng Hao, Xinpeng Yang, Hanxiao Chen, Tianwei Zhang, Haiyang Xue, Guomin Yang, Hongwei Li, Robert H. Deng

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

Imagine you are at a massive, crowded party where everyone is wearing a name tag, but the tags are slightly smudged. You want to find your friends, but you can't read the exact spelling on their tags because of the smudge. In the real world, this happens all the time: your fingerprint scanner might read your print slightly differently than last time, or a GPS app might place your car a few feet off from where it actually is. This is the problem of "fuzzy" matching—finding things that are almost the same, not exactly the same.

Now, imagine you want to find these friends without anyone else at the party knowing who you are looking for, and without you revealing your own name tag to them. This is the world of "Private Set Intersection" (PSI). It's a cryptographic magic trick where two people can compare their lists of items and find the matches, but they learn absolutely nothing about the items that didn't match. For years, scientists have been trying to build a version of this magic trick that works for "fuzzy" data (like smudged tags or slightly different fingerprints) without it taking forever to compute or requiring a supercomputer to send the results.

This paper, titled "Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching," is like a team of engineers who just invented a new, super-fast way to do this fuzzy matching magic. The authors, a group of researchers from universities in Singapore and China, argue that the old ways of doing this were too slow and clunky, like trying to find a needle in a haystack by checking every single piece of hay one by one. They propose a new system that uses clever shortcuts and "lightweight" cryptographic tools to make the process much faster and cheaper, especially when dealing with huge lists of data.

The Old Way: The Slow, Heavy Haul

To understand why this new invention is a big deal, let's look at the old methods. Previously, to find fuzzy matches securely, researchers relied on very heavy, complex cryptographic tools. Think of these tools as giant, iron-clad safes. While they are secure, they are also incredibly heavy to carry. If you wanted to compare two lists of 10,000 items, the old methods would require so much computing power and data transfer that it would feel like trying to move a mountain with a spoon.

Some newer methods tried to use lighter tools, but they had a different problem: they got slower and slower as the "fuzziness" (the allowed difference between items) increased. It was like a car that gets stuck in mud the deeper the mud gets. If you wanted to allow for a bigger smudge on the name tag, the system would grind to a halt. The authors of this paper point out that these existing methods are simply not scalable enough for real-world use, especially when you have large datasets or need to allow for larger differences.

The New Trick: Two Lightweight Tools

The authors' solution is to replace the heavy iron safes with two much lighter, more efficient tools: Oblivious Pseudorandom Functions (OPRF) and Oblivious Transfer (OT).

Imagine OPRF as a magical, unbreakable lockbox. One person puts a secret code inside, and the other person can check if a key they have opens it, but neither person learns the other's secret code. The authors created a new way to use these lockboxes that is much faster than before. Instead of checking every possible combination of "almost matches" (which is a huge number), their new method uses a "role-reversed" trick. It's like having two people swap jobs halfway through the game to compress a long list of possibilities into a single, quick check. This reduces the time needed from something that grows exponentially (getting huge very fast) to something that grows much more slowly.

The second tool, OT, is like a "secret menu" at a restaurant. The customer (receiver) wants to order a specific dish without telling the waiter (sender) which one they picked, and the waiter gives them the dish without knowing what they ordered. The authors use a customized version of this to check if two points are close enough. This is particularly good for short, simple data, like checking if two numbers are close.

The Double-Layer Filter: A Smart Search

For smaller, low-dimensional data (like a list of 2D coordinates or 3D locations), the authors introduce a brilliant new framework they call a "dual-layer hashing" system.

Imagine you are looking for a specific book in a library with millions of books. The old way was to walk down every single aisle and check every book. The authors' new method is like having a librarian who first sorts the books into big boxes (spatial hashing) and then uses a super-fast, smart sorting machine (Cuckoo hashing) to narrow it down to just a few boxes.

Here is the magic part: In the old systems, the receiver had to check against every possible box their item could be in, which meant checking millions of boxes even if the sender only had a few books. The authors realized that most of those boxes are empty! So, they built a system where the sender only puts their books into the boxes they actually occupy. The receiver then only checks those specific boxes. This turns a massive, impossible search into a tiny, manageable one. They call this "reducing the input domain," which is just a fancy way of saying, "Let's only look where the stuff actually is."

To make sure this shortcut doesn't accidentally show the wrong books (false positives), they added a final "consistency check." It's like a security guard who double-checks that the book you found is actually in the right box before letting you take it.

The Results: Speeding Up the Party

The authors didn't just build this in theory; they built it and tested it. They ran their new protocol against the best existing methods (from researchers like van Baarsen and Pu, and Piske et al.) using simulated data on a powerful server.

The results were dramatic. For low-dimensional data (like 2 to 8 dimensions), their new protocol was up to 145 times faster in running time and reduced the amount of data sent over the network by 20 times compared to the previous best method. For high-dimensional data (like 16 to 64 dimensions), they saw speedups of up to 36 times and communication reductions of up to 54 times.

They also showed that their system handles larger "fuzziness" thresholds much better. While older methods would slow down drastically as you allowed for bigger differences, their system stayed fast and efficient.

What They Didn't Do (and Why It Matters)

It's important to note what this paper doesn't claim. The authors are careful to say that their high-dimensional solution relies on a specific assumption: that the data points are "globally disjoint." In our party analogy, this means assuming that no two friends are standing so close together that their smudged name tags would overlap in a confusing way. While this is a strong assumption and might not fit every single real-world scenario, it allows them to achieve the incredible speed they did. They explicitly state that without this assumption, the problem is much harder, and they don't claim to have solved that harder version yet.

Furthermore, they didn't just suggest these ideas; they proved them mathematically and backed them up with extensive experiments. They didn't just say "it's faster"; they measured it, showing exactly how many seconds and megabytes were saved.

The Takeaway

In short, this paper presents a major step forward in making privacy-preserving fuzzy matching practical. By swapping out heavy, slow cryptographic tools for lighter, smarter ones and using a clever double-layer filtering system, the authors have built a protocol that is significantly faster and more efficient than anything currently available. While it works best under certain conditions (like the "globally disjoint" assumption for high dimensions), the results suggest that we are much closer to being able to securely match fuzzy data—like fingerprints, locations, or biometric scans—without sacrificing speed or privacy. It's a reminder that sometimes, the best way to solve a giant problem isn't to build a bigger machine, but to build a smarter one.

=== SUMMARY ===

Technical Summary: Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

1. Problem Statement

Fuzzy Private Set Intersection (fuzzy PSI) enables a sender holding a set of $d$ -dimensional points $Q$ and a receiver holding a set $W$ to privately compute the intersection where points satisfy a distance threshold $\delta$ (i.e., $\text{dist}(\mathbf{q}, \mathbf{w}) \le \delta$ ) under a given metric (e.g., $L_p$ for $p \in [1, \infty]$ ). While traditional PSI handles exact matches, fuzzy PSI is critical for noisy data applications like biometric identification and location-based services.

Existing solutions face significant scalability challenges:

Heavy Cryptographic Primitives: Many protocols rely on expensive homomorphic encryption (AHE) or garbled circuits (GCs), leading to prohibitive concrete overhead.
Poor Asymptotic Complexity: State-of-the-art lightweight protocols (e.g., van Baarsen and Pu [46]) often incur complexities scaling as $O((\log \delta)^d)$ or $O(\delta)$ for the distance threshold $\delta$ and dimension $d$ . This creates severe bottlenecks for large $\delta$ or high-dimensional data.
Quadratic Overhead: Pairwise comparison results in $O(mn)$ complexity, which is impractical for large sets.

The authors pose the question: Can we construct scalable fuzzy PSI protocols with both concrete and asymptotic efficiency guarantees for general $L_p$ distances across both low- and high-dimensional sets?

2. Methodology

The paper proposes a suite of protocols built on two core technical innovations: Asymptotically Efficient Fuzzy Matching and a Dual-Layer Hashing Framework.

2.1 Asymptotically Efficient Fuzzy Matching

The authors design two single-point fuzzy matching protocols to securely evaluate $\text{dist}(\mathbf{q}, \mathbf{w}) \le \delta$ :

Role-Reversed OPRF Protocol:
- Mechanism: This protocol improves upon previous OPRF-based approaches (which used prefix tries to reduce sender programming but increased receiver computation to $O((\log \delta)^{d/2})$ ). The authors introduce a two-step role-reversed OPRF mechanism.
- Process:
  1. The sender programs an OPRF mapping interval prefixes to random values.
  2. The receiver evaluates these to get a set of values.
  3. Innovation: The roles are reversed for a second OPRF invocation. The receiver programs a new OPRF mapping the first round's outputs to a single value, while the sender evaluates it.
- Result: This compresses the receiver's $O(\log \delta)$ evaluations into a single value per dimension, reducing computational overhead from $O((\log \delta)^d)$ to $O(d \log \delta)$ .
Customized OT Protocol:
- Mechanism: Designed for inputs with short bit lengths ( $\ell$ ), this protocol leverages Oblivious Transfer (OT) to compute the most significant bit (MSB) and AND operations directly.
- Result: It achieves $O(d \ell)$ overhead. When combined with domain reduction (see below), it offers superior concrete performance by eliminating the statistical security parameter $\lambda$ dependency inherent in OPRF-based constructions.

2.2 Fuzzy PSI Frameworks

For Low-Dimensional Sets

The authors propose a Dual-Layer Hashing Framework combining Spatial Hashing and Cuckoo Hashing:

Spatial Hashing: Partitions the $d$ -dimensional space into grid cells of side length $2\delta$ .
Dual-Layer Optimization:
- Instead of the receiver checking all $2^d$ neighboring cells for every point (leading to $O(2^d n)$ fuzzy matching invocations), the authors observe that only cells containing sender points are relevant.
- Cuckoo Hashing: The sender maps its points to a table. The receiver maps its potential neighbor cells to the same table.
- Reduction: This reduces the number of required fuzzy matching invocations from $O(2^d n)$ to $O(m)$ .
Domain Reduction & Consistency Check: To utilize the efficient OT-based matching, the input domain is reduced to the local neighborhood of a sender point (a hypercube of side $6\delta$ ). To prevent false positives caused by this small domain (where random values might accidentally fall within $\delta$ ), an additional consistency check verifies that the sender's point and the receiver's point map to the exact same grid cell.

For High-Dimensional Sets

To avoid the exponential $2^d$ blowup, the authors construct protocols based on the Globally Disjoint Assumption (projections of balls do not overlap in any dimension).

Mechanism: They compile the OPRF-based fuzzy matching into a multi-point PSI.
Filtering: The protocol first generates unique identifiers based on $L_\infty$ distance. Since $L_\infty$ bounds $L_p$ , these identifiers act as a coarse filter. Only pairs with matching identifiers undergo rigorous $L_p$ distance checks.
Complexity: This achieves asymptotic overhead linear in set sizes ( $m, n$ ), dimension ( $d$ ), and logarithmic in the threshold ( $\log \delta$ ), i.e., $O((m+n)d \log \delta)$ .

3. Key Contributions

Asymptotically Efficient Fuzzy Matching:
- A role-reversed OPRF protocol achieving $O(d \log \delta)$ overhead, improving upon the $O((\log \delta)^d)$ of prior works.
- An OT-based protocol with $O(d \ell)$ overhead, suitable for short inputs.
New Low-Dimensional Framework:
- A dual-layer hashing framework (Spatial + Cuckoo) that reduces fuzzy matching invocations from $O(2^d n)$ to $O(m)$ .
- An input space reduction optimization with a consistency check to enable efficient OT-based matching without false positives.
Improved High-Dimensional Protocols:
- Protocols for high-dimensional sets under the globally disjoint assumption, achieving linear complexity in $d$ and $O(\log \delta)$ in the threshold.
Extensive Evaluations:
- Comprehensive benchmarks across $L_\infty, L_1,$ and $L_2$ metrics for dimensions $d \in [2, 64]$ and thresholds $\delta \in [16, 1024]$ .

4. Experimental Results

The authors implemented their protocols and compared them against state-of-the-art works: van Baarsen and Pu [46] (OPRF-based) and Piske et al. [38] (OPRF & OT-based).

Low-Dimensional Performance ( $d \in [2, 8]$ ):
- Speedup: Up to 145 $\times$ faster running time compared to [46] and 25 $\times$ faster than [38].
- Communication: Up to 20 $\times$ reduction in communication cost compared to [46] and 17 $\times$ compared to [38].
- Scalability: Unlike [46], whose runtime grows with $(\log \delta)^{d/2}$ , the proposed protocol's performance remains nearly constant as $\delta$ increases.
High-Dimensional Performance ( $d \in [16, 64]$ ):
- Speedup: Up to 36 $\times$ faster running time compared to [46].
- Communication: Up to 54 $\times$ reduction in communication cost compared to [46].
- The advantage is particularly pronounced for large distance thresholds ( $\delta$ ), where prior protocols suffer from linear or super-linear scaling in $\delta$ .

5. Significance and Claims

The paper claims to advance the state of fuzzy PSI both concretely and asymptotically:

Asymptotic Improvement: It resolves the $O((\log \delta)^d)$ and $O(\delta)$ bottlenecks of previous lightweight protocols, offering $O(d \log \delta)$ and linear dependencies on set sizes.
Concrete Efficiency: By combining role-reversed OPRF, OT, and a novel dual-layer hashing framework, the protocols achieve massive practical speedups and communication reductions, making fuzzy PSI viable for larger thresholds and higher dimensions than previously possible.
Generality: The solution supports general $L_p$ distances ( $p \in [1, \infty]$ ) for both low- and high-dimensional settings, whereas many prior works were limited to specific metrics (e.g., $L_\infty$ only) or required heavy cryptographic assumptions.

The authors emphasize that while the high-dimensional protocols rely on the strong "globally disjoint" assumption, the low-dimensional protocols operate under weaker, more practical assumptions (unique center/ball per grid cell) consistent with prior efficient works.