💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

This paper presents new Fuzzy Private Set Intersection (FPSI) protocols for general $L_p$ distances that achieve optimal logarithmic dependence on the distance threshold $\delta$ using only oblivious transfer and symmetric-key primitives, thereby eliminating the need for expensive homomorphic encryption while significantly outperforming state-of-the-art solutions in runtime and communication.

Original authors: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Published 2026-06-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

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 two people, Alice and Bob, who want to find out if they have any "similar" items in their respective collections without showing each other their entire lists.

The Problem: In a standard game, they would only match items that are exactly the same (e.g., both have a "Red Apple").
The Twist (Fuzzy PSI): In this new game, they want to match items that are close enough. For example, if Alice has a "Red Apple" and Bob has a "Slightly Bruised Red Apple," they should count as a match. The rule is: "If the difference between our items is smaller than a specific distance (let's call it the Threshold), we match."

The challenge is doing this securely. Alice shouldn't learn Bob's whole list, and Bob shouldn't learn Alice's whole list. They only want to know which items are close enough.

The Old Way: The Slow, Expensive Search

Previous methods for this "Fuzzy Matching" game had two big problems:

The "Linear" Trap: If the "closeness" threshold was large (say, 100 units), the computers had to check 100 different possibilities for every single item. It was like searching for a needle in a haystack by checking every single straw one by one. The bigger the threshold, the slower it got.
The "Heavy Machinery" Problem: To make this work securely, old methods used very heavy, slow cryptographic tools (like Additive Homomorphic Encryption). Think of this as trying to send a secret message using a massive, fuel-guzzling truck when a bicycle would do.

The New Breakthrough: The "Prefix" Shortcut

This paper introduces a new way to play the game that is fast, lightweight, and smart.

1. The "Zip Code" Analogy (Prefixes)

Instead of checking every single number in a range (like checking if a number is 10, 11, 12... up to 100), the authors use a trick called Prefixes.

Imagine you are looking for a house in a city.

Old Way: You knock on every door in the neighborhood to see if the resident is your friend.
New Way: You look at the Zip Code. If your friend lives in "10001," you only need to check houses with that prefix. You don't need to check the whole city.

The authors realized that any "range" of numbers (the threshold) can be broken down into just a few "Zip Codes" (prefixes).

The Magic: The time it takes to check these prefixes doesn't grow with the size of the threshold; it grows logarithmically.
- If the threshold doubles, the work only adds a tiny bit.
- If the threshold gets 100 times bigger, the work only doubles.
- Analogy: It's like finding a book in a library. Checking every book takes forever. Checking the shelf label (prefix) takes seconds, no matter how many books are on the shelf.

2. The "Lightweight" Tools (Symmetric Primitives)

The authors replaced the heavy "trucks" (expensive encryption) with "bicycles" (symmetric-key primitives and Oblivious Transfer).

Oblivious Transfer (OT): Imagine a waiter who can give you one of two secret menu items without you knowing which one you picked, and without the waiter knowing which one you wanted. The authors use this to swap information securely without revealing the whole list.
The Result: Their system is built entirely from these lightweight, fast tools.

The Two Scenarios: Small Rooms vs. Giant Halls

The paper offers two different strategies depending on how "crowded" the data is (dimensionality):

Scenario A: Low Dimensions (The "Apart" Assumption)

The Setting: Think of a small room where people are standing far apart from each other (at least 2x the threshold distance).
The Strategy: They use Spatial Hashing. Imagine dividing the room into a grid of tiles. If two people are close, they must be in the same tile or neighboring tiles. The protocol only checks those specific tiles.
The Innovation: They combined this grid system with their new "Prefix" shortcut and a special "Equality Check" tool (called ECSS). This allows them to find matches instantly without checking every single pair.

Scenario B: High Dimensions (The "Separate" Assumption)

The Setting: Think of a massive, multi-dimensional warehouse. In high dimensions, dividing the space into a grid creates too many empty tiles (the "curse of dimensionality").
The Strategy: They use Distributed ID Generation. Instead of a grid, they give every item a unique "ID card" based on its location.
The Innovation: They created a new way to generate these IDs securely using their "Prefix" trick. Even in a giant warehouse, they can generate these IDs so that if two items are close, their IDs will match, without revealing the items' actual locations.

The "Secret Sauce": Equality Conditional Sum

The core of their invention is a new mathematical tool called Equality Conditional Sum (ECSS).

How it works: Imagine Alice and Bob both have a list of numbers. They want to add up the numbers only if a specific condition is met (e.g., "Only add the numbers if the prefixes match").
The Magic: They can do this addition securely without either party revealing their numbers. If the prefixes don't match, the result is just random noise. If they do match, the result is the correct sum. This allows them to verify if items are close without ever seeing the actual values.

The Results: A Massive Speedup

The authors built a working version of their system and tested it against the best existing methods.

Speed: Their system is up to 43.7 times faster than the previous best.
Data Usage: It uses up to 31.3 times less data to send over the network.
Scalability: While other systems crashed (ran out of memory) when the data sets got very large, their system kept running smoothly.

Summary

In short, this paper solves the "Fuzzy Matching" problem by:

Replacing slow, heavy encryption with fast, lightweight tools.
Using "Prefixes" (like Zip Codes) to turn a slow, linear search into a fast, logarithmic one.
Creating new "Secret Sum" tools that let two parties check for closeness without revealing their secrets.

The result is a system that can find "similar" items in massive, private datasets almost instantly, making privacy-preserving data matching practical for the first time at a large scale.

Technical Summary: Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

Problem Statement
Fuzzy Private Set Intersection (FPSI) enables a sender with a set of $d$ -dimensional vectors $Q$ and a receiver with a set $W$ to identify items $q \in Q$ such that there exists a $w \in W$ with $\text{dist}(q, w) \le \delta$ , without revealing additional information. While standard PSI has achieved high efficiency, existing FPSI protocols face significant theoretical and practical bottlenecks. Prior works typically exhibit linear scaling with the distance threshold $\delta$ (i.e., $O(\delta)$ ), or achieve poly-logarithmic dependence only for $L_\infty$ distances. Protocols supporting general Minkowski distances ( $L_p$ for $p \in [1, \infty]$ ) with logarithmic dependence on $\delta$ have either relied on expensive Additive Homomorphic Encryption (AHE) or suffered from security flaws and exponential complexity terms in the dimension $d$ . The goal is to achieve exact logarithmic dependence on $\delta$ for general $L_p$ distances using only efficient symmetric-key primitives.

Methodology and Core Techniques
The authors propose new FPSI protocols built entirely from Oblivious Transfer (OT) and symmetric-key primitives, avoiding public-key operations like AHE. The construction relies on two primary assumptions: the apart assumption (suitable for low-dimensional settings) and the separate assumption (suitable for high-dimensional settings).

Prefix Representation and Interval Testing:
The core innovation replaces the enumeration of all integers in an interval $[q_k - \delta, q_k + \delta]$ (which costs $O(\delta)$ ) with a prefix representation using $O(\log \delta)$ prefixes. This reduces the interval testing cost to $O(\log \delta)$ per dimension.
Equality Conditional Sum/Inner-Product Share (ECSS/ECIPS):
To handle the interaction required by prefix matching without revealing the sender's input or incurring exponential overhead, the authors introduce two new cryptographic primitives:
- Equality Conditional Sum Share (ECSS): Used for $L_\infty$ distance. It allows parties to compute a sum of values conditional on an equality match between input vectors, outputting secret shares of the result.
- Equality Conditional Inner-Product Share (ECIPS): Used for general $L_p$ distances. It computes an inner product conditional on equality, enabling the calculation of $|w_k - q_k|^p$ via binomial expansion without revealing the specific terms.
  Both primitives are implemented efficiently using OT, Oblivious Programmable PRFs (OPPRF), and Permute+Share (PS) protocols.
Handling Multiple Elements:
- Low-Dimensional ( $L_\infty$ and $L_p$ ): The protocols utilize spatial hashing (grid cells) combined with Cuckoo hashing to reduce the number of pairwise comparisons. The authors introduce optimizations using shared OPRF (sOPRF) to eliminate the need for dummy values in empty bins, thereby hiding the sender's hashing positions and removing the need for global permutation steps in certain configurations.
- High-Dimensional ( $L_\infty$ and $L_p$ ): To avoid the exponential $O(2^d)$ cost of spatial hashing, the authors employ a Distributed ID Generation (dIDG) protocol. This protocol generates unique IDs for elements such that close elements share an ID. The authors identify security flaws in prior dIDG constructions (specifically in [DZL25]) related to collision leakage and propose a secure, symmetric-key-based dIDG using sOPRF and ECSS.

Key Contributions

New Primitives: The introduction of ECSS and ECIPS, which enable efficient fuzzy matching with exact logarithmic dependence on $\delta$ using only symmetric primitives.
Optimal Complexity: The first FPSI protocols for general $L_p \in [1, \infty]$ distances that achieve strictly logarithmic complexity $O(d \log \delta)$ in the threshold $\delta$ . This is theoretically optimal, as distinguishing values in an interval of length $O(\delta)$ requires $\Omega(\log \delta)$ bits of information.
Security and Efficiency: The protocols eliminate reliance on AHE, replacing it with OT and symmetric-key operations. The authors also identify and fix security vulnerabilities in recent prefix-based protocols (e.g., [DZL25]) that suffered from mask reuse and collision leakage.
Scalable Constructions: Separate constructions for low-dimensional (using spatial hashing) and high-dimensional (using dIDG) settings, both achieving optimal asymptotic complexity.

Experimental Results
The authors implemented their protocols and compared them against state-of-the-art works ([GQL+24], [DZL25], [BGMP25]).

Performance: The new protocols outperform prior art significantly. In low-dimensional settings, they achieve up to 43.7× faster runtime and 31.3× lower communication overhead.
Scalability: While prior works like [GQL+24] and [DZL25] encountered memory overflow at set sizes of $2^{16}$ in high-dimensional settings, the proposed protocols executed successfully under the same configurations.
Threshold Dependence: The experiments confirm that the runtime and communication costs scale logarithmically with $\delta$ , contrasting with the linear scaling observed in previous linear-dependence protocols.

Significance
The paper claims a theoretical breakthrough in optimal threshold scaling for FPSI, demonstrating that exact logarithmic dependence on $\delta$ is achievable for general $L_p$ distances without costly public-key cryptography. Practically, this advances the feasibility of scalable FPSI applications in domains requiring fuzzy matching, such as genomic sequence matching, similar image retrieval, and compromised credential detection, by removing the efficiency bottlenecks associated with the distance threshold and dimensionality.