💻 computer science

Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

This paper proposes highly efficient Fuzzy Private Set Intersection protocols for $L_p$ distance metrics that leverage secret-shared oblivious programmable PRFs and a prefix technique to achieve linear complexity and significantly outperform state-of-the-art constructions in both running time and communication cost.

Original authors: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

Published 2026-04-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, 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

The Big Picture: The "Fuzzy" Matchmaking Problem

Imagine you and your friend are trying to find common ground, but you can't show each other your lists.

The Scenario: You have a list of your favorite songs (Set A). Your friend has a list of their favorite songs (Set B).
The Standard Problem (Exact Match): You want to know which songs are exactly the same. This is easy. You just check if "Song X" in your list is "Song X" in theirs.
The "Fuzzy" Problem: Now, imagine your lists aren't just songs, but fingerprints or face scans.
- Your fingerprint might be slightly smudged today.
- Your friend's face scan might be taken in different lighting.
- They aren't exactly the same, but they are "close enough" to be the same person.
- The Goal: You want to find these "close enough" matches without ever revealing your actual fingerprints or faces to each other.

The Challenge: Doing this securely is usually like trying to solve a massive puzzle where every piece costs a fortune to move. Previous methods were slow, expensive, and required heavy "mathematical armor" (complex encryption) that made them impractical for real-world use.

The Authors' Solution: A New, Lightweight Toolkit

The researchers (Yang, Hao, et al.) built a new system that is fast, cheap, and secure. They replaced the heavy "mathematical armor" with a set of clever, lightweight tricks.

Here is how they did it, broken down into three main ideas:

1. The "Secret Handshake" (so-OPPRF)

The Analogy: Imagine you and a friend want to check if you both know a secret password, but you don't want to say the password out loud, and you don't want to know the other person's password either.

Old Way: You would both write your passwords on a piece of paper, lock them in a heavy steel safe (expensive encryption), and mail them to a third party to check. This takes forever.
The New Way (so-OPPRF): You and your friend use a special "magic notebook."
- You write down your list of "potential matches" in the notebook.
- Your friend asks, "Is 'X' in your notebook?"
- The notebook gives you both a split secret. You get half the answer, and they get the other half.
- The Magic: Neither of you knows the full answer alone. You only know the answer when you combine your halves. If the answer is "Yes, they match," you both get a specific signal. If "No," you get random noise.
- Why it's great: This uses simple math (like adding numbers) instead of complex encryption, making it incredibly fast.

2. The "Two-Step Filter" (Coarse then Fine)

The Analogy: Imagine you are looking for a lost dog in a huge city. You don't check every single house one by one; that would take years.

Step 1: The Neighborhood Check (Coarse Mapping):
- You divide the city into neighborhoods. If the dog is in "Neighborhood A," you only check houses in Neighborhood A.
- In the paper, they turn every fingerprint into a "Neighborhood ID." If two fingerprints are close, they get the same ID.
- Risk: Sometimes, two different dogs might live in the same neighborhood (False Positive).
Step 2: The Doorstep Check (Refined Filtering):
- Now, you only check the specific houses in that neighborhood. You look closely at the dog to see if it's really the one you want.
- In the paper, they use the "Secret Handshake" (from step 1) to do this final check. If the fingerprints are truly close, the handshake confirms it. If they are just "neighborhood neighbors" but not a match, the handshake fails.

3. The "Zip Code" Trick (Prefix Optimization)

The Analogy: Imagine you are searching for a house with a street number between 100 and 200.

Old Way: You check every single number: 100, 101, 102... all the way to 200. That's 100 checks!
The New Way (Prefix): You realize you don't need to check every number. You just need to check the "prefixes" (the first few digits).
- Instead of checking 100 numbers, you check a few "blocks" (like "10x", "11x", "12x").
- This turns a task that takes 100 steps into a task that takes only 7 or 8 steps.
- Why it matters: When the "distance" allowed is large (e.g., a very blurry fingerprint), this trick makes the system exponentially faster.

The Results: Why Should We Care?

The researchers tested their new system against the current "best" methods (which are like using a steam engine to power a race car).

Speed: Their system is 12 to 145 times faster.
- Analogy: If the old system took 10 minutes to find a match, the new system does it in 4 seconds.
Data Usage: Their system uses 3 to 8 times less data to send over the internet.
- Analogy: Instead of sending a truckload of bricks, they send a single envelope.
Scalability: It works great even when you have millions of items or very high-dimensional data (like complex 3D face scans).

Summary in One Sentence

The authors invented a new, super-fast way for two people to find "close enough" matches in their secret lists (like fingerprints or medical data) without ever revealing the data, by using clever "split-secret" math tricks and "zip code" shortcuts to avoid expensive, slow encryption.

Why This Matters for You

This technology could make biometric security (unlocking phones with faces/fingers) much more private. It could also help hospitals compare patient records to find common diseases without exposing private medical histories, or help banks detect fraud without sharing customer data. It turns a theoretical "impossible" privacy problem into a practical, everyday tool.

1. Problem Statement

Private Set Intersection (PSI) allows two parties (a Sender with set $Q$ and a Receiver with set $W$ ) to compute the intersection $Q \cap W$ without revealing non-intersecting elements. Fuzzy PSI (FPSI) extends this to scenarios where exact matching is insufficient (e.g., biometric authentication), allowing the Receiver to learn items $q \in Q$ if there exists a $w \in W$ such that $dist(q, w) \le \delta$ under a distance metric (typically $L_p$ where $p \in [1, \infty]$ ).

Current Limitations:

High Complexity: Existing FPSI protocols for general $L_p$ distances often suffer from exponential complexity in the element dimension $d$ or super-linear complexity in the distance threshold $\delta$ .
Inefficiency: State-of-the-art linear-complexity protocols (e.g., Gao et al. [14], Dang et al. [16]) rely heavily on Additively Homomorphic Encryption (AHE) (e.g., ElGamal, Paillier). These public-key operations are computationally expensive, leading to poor practical performance compared to symmetric-key approaches.
Scalability: High-dimensional data and large distance thresholds ( $\delta$ ) render existing solutions prohibitively slow and communication-heavy.

2. Methodology

The authors propose a new framework for FPSI that achieves linear complexity in set sizes ( $m, n$ ), dimension ( $d$ ), and threshold ( $\delta$ ), primarily using lightweight symmetric-key operations. The core methodology involves three main components:

A. New Building Block: Shared-Output OPPRF (so-OPPRF)

The paper introduces Oblivious Programmable Pseudorandom Function with Secret-Shared Outputs (so-OPPRF).

Functionality: Unlike standard OPPRF where the receiver learns the output, so-OPPRF outputs secret shares of the PRF value to both parties. Neither party learns the full value individually.
Construction: It combines an Oblivious Key-Value Store (OKVS) with a Shared-Output OPRF (so-OPRF).
- The Sender programs the PRF on specific points using OKVS encoding.
- The Receiver queries inputs and receives secret shares of the result.
- This avoids the leakage of partial match information that occurs in standard OPPRF, which previously required expensive AHE to mask.

B. Modular Fuzzy Mapping

The authors design a modular protocol for the "coarse mapping" phase (assigning identifiers to elements within distance $\delta$ ):

Local Mapping: Both parties generate local identifiers based on intervals of size $2\delta$ . To prevent information leakage regarding interval overlaps, they use so-OPPRF to retrieve secret shares of random values associated with these intervals.
Global Mapping: To combine local mappings into a global ID without revealing the underlying values, they introduce Secret-Shared Input OPRF (si-OPRF). Both parties hold secret shares of the key and the input. The Receiver learns the final ID, while the Sender learns its own IDs, ensuring that elements within distance $\delta$ receive identical IDs without leaking intermediate values.

C. Refined Filtering

After coarse mapping, false positives (elements with the same ID but distance $> \delta$ ) must be eliminated.

The parties use so-OPPRF again to compute secret shares of the distance (or 0 for $L_\infty$ ).
They employ a Private Equality Test (PEQT) or Private Interval Test to verify if the shared distance is within the threshold.
Finally, an Oblivious Transfer (OT) protocol allows the Receiver to retrieve the matching Sender elements.

D. Prefix Optimization

For large distance thresholds ( $\delta$ ), the linear dependence on $\delta$ is optimized to logarithmic ( $O(\log \delta)$ ) using prefix representation.

Instead of programming the entire interval $[q-\delta, q+\delta]$ (size $2\delta+1$ ), the Sender programs only $O(\log \delta)$ prefixes that cover the interval.
This significantly reduces communication and computation costs for large $\delta$ .

3. Key Contributions

so-OPPRF: A novel cryptographic primitive enabling oblivious evaluation of programmable PRFs with secret-shared outputs, serving as a foundational block for efficient fuzzy matching.
Efficient FPSI Protocols: The first FPSI protocols for general $L_p$ ( $p \in [1, \infty]$ ) distances that achieve linear complexity in $m, n, d,$ and $\delta$ using symmetric-key primitives (PRF, OT, OKVS) instead of AHE.
Prefix Optimization: An adaptation of prefix techniques to reduce complexity from $O(\delta)$ to $O(\log \delta)$ for large thresholds, maintaining efficiency without heavy public-key operations.
Modular Design: A clear separation of fuzzy mapping and filtering phases, simplifying protocol analysis and implementation.

4. Experimental Results

The authors implemented the protocols in C++ and compared them against state-of-the-art works: Gao et al. (ASIACRYPT'24) and Dang et al. (CCS'25).

Performance Gains:
- Running Time: Achieved a speedup of 12 $\times$ to 145 $\times$ compared to Gao et al. and 9 $\times$ to 80 $\times$ compared to Dang et al.
- Communication: Reduced communication costs by 3 $\times$ to 8 $\times$ (vs. Gao) and 5 $\times$ to 19 $\times$ (vs. Dang).
Scalability: The performance gap widens with larger set sizes and dimensions. For example, with $m=n=2^{16}$ , $d=8$ , and $\delta=32$ , the proposed protocol is 145 $\times$ faster than Gao et al.
Prefix Optimization: For large $\delta$ (e.g., $\delta=1024$ ), the prefix-optimized version reduced communication by 11 $\times$ and running time by ~50% compared to the non-prefix version, while still outperforming competitors.

5. Significance

Practical Viability: By replacing expensive homomorphic encryption with symmetric-key operations, this work makes Fuzzy PSI practically viable for real-world applications like biometric authentication (fingerprint/face recognition) and genome matching, where high-dimensional data and noise tolerance are critical.
Theoretical Advancement: It resolves the open question of whether concretely efficient FPSI with linear complexity is possible without AHE, providing a new paradigm for secure multi-party computation in fuzzy matching scenarios.
Future Impact: The introduced so-OPPRF and si-OPRF primitives are likely to be useful building blocks for other privacy-preserving protocols requiring secret-shared evaluations.

Limitations & Future Work:
The current protocol relies on the disjoint projection assumption (elements are sufficiently far apart in at least one dimension). Future work aims to relax these assumptions and achieve malicious security without significant efficiency loss.