Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

Based on the paper, here is a detailed summary:

This paper presents scalable fuzzy private set intersection (fuzzy PSI) protocols for general Lp ∈ [1,∞] distance, supporting both low- and high-dimensional sets. In fuzzy PSI, a sender holds a set of d-dimensional points Q = q1,..., qm and a receiver holds a set W = w1,..., wn. The goal is for the receiver to learn the point q ∈ Q for which there exists some w ∈ W satisfying dist(q, w) ≤ delta under a given distance metric.

The paper identifies that prior fuzzy PSI protocols have significant efficiency issues because they either heavily rely on expensive cryptographic primitives like homomorphic encryption or garbled circuits, or incur undesirable asymptotic communication and computation complexity. The core contribution is two new efficient fuzzy matching protocols that securely evaluate dist(q, w) ≤ delta.

The first fuzzy matching protocol is built from a role-reversed oblivious PRF (OPRF) and achieves O(d log delta) overhead, compared to O((log delta)d) in previous works. This is achieved by using two role-reversed invocations of programmable OPRF (OPPRF) to compress the prefix representations of intervals, avoiding the computational bottleneck of comparing all possible combinations.

The second fuzzy matching protocol leverages customized oblivious transfer (OT) with O(dl) overhead, where l is the bit length of inputs. This approach is particularly suitable for short inputs and eliminates the hidden dependence on the statistical security parameter lambda inherent in OPRF-based constructions.

For low-dimensional sets, the paper proposes a new dual-layer hashing framework that combines spatial hashing with Cuckoo hashing. This framework reduces the number of fuzzy matching invocations from O(2dn) in prior works to just O(m), by filtering the candidate space down to approximately m pairs of points. The protocol is instantiated with the OT-based fuzzy matching and enhanced with a domain reduction optimization, which restricts operations to a smaller hypercube of side length 6delta. To address false positives introduced by this small input domain, an additional consistency check is integrated to verify that the cell containing the sender’s point is identical to the cell intersected by the receiver’s point.

For high-dimensional sets, the paper constructs fuzzy PSI protocols based on both the OPRF- and OT-based fuzzy matching. These protocols achieve an asymptotic overhead linear with n, m, d, and log delta but rely on the strong globally disjoint assumption on both parties’ sets.

The protocols achieve an overhead linear with n, m, log delta, 2d, without the O((log delta)d) or O(delta) factors present in prior works. Extensive evaluations demonstrate that the protocols achieve up to a 145× speedup in running time and a 20× reduction in communication cost compared to van Baarsen and Pu (ASIACRYPT’25), and achieve up to a 25× speedup in running time and up to a 17× reduction in communication cost compared to Piske et al. (CCS’25). In high-dimensional settings, for dimensions d ranging from 16 to 64, the protocols require up to 36× less running time and up to 54× less communication.

Improvements to AI Systems:

1. Efficient Secure Multi-Party Computation (SMPC) for AI Models: Integrate the new fuzzy PSI protocols into privacy-preserving machine learning pipelines. The improved AI system can perform secure nearest-neighbor search, clustering, or dataset joining across distributed parties without revealing raw data, with up to 145× faster runtime and 20× lower communication than prior methods, enabling real-time collaborative AI on sensitive data (e.g., healthcare records, financial transactions).

2. Scalable Fuzzy Matching in High-Dimensional Embedding Spaces: Use the high-dimensional fuzzy PSI construction (linear in n, m, d, delta) to enable AI systems to match user queries or data points against large reference databases (e.g., biometric templates, image embeddings) under L p distance metrics. The improved system can handle dimensions 16–64 with up to 36× less runtime and 54× less communication, making it practical for on-device or edge AI where bandwidth is limited.

3. Privacy-Preserving Data Deduplication and Record Linkage: Apply the dual-layer hashing framework (spatial + Cuckoo hashing) to AI systems that need to deduplicate or link records across organizations (e.g., fraud detection, census data). The improved system reduces candidate comparisons from O(2 d n) to O(m), allowing AI to process millions of records with minimal false positives, while maintaining strict privacy guarantees—enabling secure cross-institutional AI training without data centralization.

4. Secure AI Inference with Approximate Matching: Leverage the OT-based fuzzy matching (with O(d) overhead) to build AI systems that perform secure inference on short, low-dimensional inputs (e.g., IoT sensor data, location coordinates). The improved system can run real-time, privacy-preserving anomaly detection or personalized recommendations with no hidden dependence on security parameters, making it suitable for latency-sensitive applications like autonomous vehicles or smart grids.

5. Optimized Cryptographic Backend for AI Frameworks: Replace expensive homomorphic encryption or garbled circuits in existing privacy-preserving AI libraries with the new role-reversed OPRF and OT protocols. The improved AI system can natively support secure L p distance computations (including L 1, L 2, L infinity) in frameworks like PyTorch or TensorFlow, reducing computational overhead for tasks like secure k-NN classification or private set operations, and enabling broader adoption of privacy-preserving AI in resource-constrained environments.

In this paper, we present scalable fuzzy PSI protocols for general L p in [1, infinity] 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 delta) overhead, compared to O((delta) d) in previous works. The second leverages customized oblivious transfer (OT) with O(d) overhead, where 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, delta, 2 d, without the O((delta) d) or O(delta) 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 delta 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).