Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

arXiv:2608.11526v1 [cs.CR] 12 Aug 2026

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching Meng Hao

Xinpeng Yang

Hanxiao Chen∗

Singapore Management University Singapore menghao303@gmail.com

Nanyang Technological University Singapore XINPENG004@e.ntu.edu.sg

University of Electronic Science and Technology of China Chengdu, China hanxiao.chen@uestc.edu.cn

Tianwei Zhang

Haiyang Xue

Guomin Yang

Nanyang Technological University Singapore tianwei.zhang@ntu.edu.sg

Singapore Management University Singapore haiyangxue@smu.edu.sg

Singapore Management University Singapore gmyang@smu.edu.sg

Hongwei Li∗

Robert H. Deng

University of Electronic Science and Technology of China Chengdu, China hongweili@uestc.edu.cn

Singapore Management University Singapore robertdeng@smu.edu.sg

Abstract In fuzzy private set intersection (fuzzy PSI), there are two parties, a sender holding a set of 𝑑-dimensional points 𝑄 = {𝒒 1, . . . , 𝒒𝑚 } and a receiver holding a set 𝑊 = {𝒘1, . . . , 𝒘𝑛 } of the same structure. It enables the receiver to learn the point 𝒒 ∈ 𝑄 for which there exists some 𝒘 ∈ 𝑊 satisfying dist(𝒒, 𝒘) ≤ 𝛿 under a given distance metric. Although several fuzzy PSI protocols for 𝐿𝑝 ∈ [1,∞] distance are proposed, there are significant efficiency issues, mainly because they (1) heavily rely on expensive cryptographic primitives, e.g., homomorphic encryption or garble circuits, and/or (2) incur undesirable asymptotic communication and computation complexity. In this paper, we present scalable fuzzy PSI protocols for general 𝐿𝑝 ∈ [1,∞] distance, supporting both low- and high-dimensional sets. The core technique is two efficient fuzzy matching protocols that securely evaluate dist(𝒒, 𝒘) ≤ 𝛿. The first is built from a role-reversed oblivious PRF (OPRF) and realizes 𝑂 (𝑑 log 𝛿) overhead, compared to 𝑂 ((log 𝛿)𝑑 ) in previous works. The second leverages customized oblivious transfer (OT) with 𝑂 (𝑑ℓ) 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 𝑛, 𝑚, log 𝛿, 2𝑑 , without the 𝑂 ((log 𝛿)𝑑 ) or 𝑂 (𝛿) 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 𝑛, 𝑚, 𝑑, and log 𝛿 but rely on the strong globally disjoint assumption. ∗ Corresponding authors.

This work is licensed under a Creative Commons Attribution 4.0 International License. CCS ’26, The Hague, Netherlands © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2871-6/2026/11 https://doi.org/10.1145/3830454.3832667

Extensive evaluations demonstrate that our 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).

CCS Concepts • Security and privacy → Cryptography.

Keywords Fuzzy Private Set Intersectionl; Fuzzy Matching ACM Reference Format: Meng Hao, Xinpeng Yang, Hanxiao Chen, Tianwei Zhang, Haiyang Xue, Guomin Yang, Hongwei Li, and Robert H. Deng. 2026. Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching. In Proceedings of the 2026 ACM SIGSAC Conference on Computer and Communications Security (CCS ’26), November 15–19, 2026, The Hague, Netherlands. ACM, New York, NY, USA, 23 pages. https://doi.org/10.1145/3830454.3832667

1

Introduction

Private set intersection (PSI), including [14, 15, 18, 29, 30, 34–37, 39, 43] and references therein, has been extensively studied over the past decades. It enables a sender S holding a set 𝑄 and a receiver R holding a set 𝑊 to privately compute the intersection 𝑄 ∩ 𝑊 , while revealing no additional information beyond the output. Traditional PSI protocols focus on exact item matching and have been successfully deployed in applications such as private contact discovery [28, 47] and password breach monitoring [20]. However, these protocols are inherently limited in scenarios that require approximate matching, such as location-based services and biometric identification. To address this gap, a lot of fuzzy PSI protocols [3, 7, 8, 11, 16, 17, 19, 38, 42, 45, 46, 50] have been proposed. In fuzzy PSI, the sender holds a set of 𝑑-dimensional points 𝑄 = {𝒒 1, . . . , 𝒒𝑚 } and the receiver holds 𝑊 = {𝒘 1, . . . , 𝒘𝑛 } of the same structure. It enables the receiver to learn the point 𝒒 ∈ 𝑄 for which there exists some

CCS ’26, November 15–19, 2026, The Hague, Netherlands

𝒘 ∈ 𝑊 satisfying dist(𝒒, 𝒘) ≤ 𝛿 under a given distance metric dist, e.g., Chebyshev distance 𝐿∞ or Minkowski distance 𝐿𝑃 . Fuzzy PSI is particularly useful in scenarios where inputs are inherently noisy. For example, in biometric identification, users are matched against biometric samples such as iris scans, fingerprints, or facial patterns. Similarly, in ride-sharing applications, passengers determine whether there are available vehicles within a certain proximity. A naive approach to fuzzy PSI is to perform pairwise comparisons between elements of the two sets. However, it incurs a quadratic overhead of 𝑂 (𝑚𝑛) in the set sizes, making it impractical for largescale sets. To avoid the efficiency issue, existing fuzzy PSI protocols, as illustrated by Gao et al. [16], follow a common paradigm with two phases: coarse mapping and refined filtering. (1) In the coarse mapping phase, initial pairings are established between a sender point 𝒒 and a receiver point 𝒘 if they are potentially 𝛿-close, through some fuzzy mapping scheme. However, this phase may introduce false positives, that is, two points with a distance greater than 𝛿 can still be paired. (2) In the refined filtering phase, a fuzzy matching approach is applied to each pair formed during the coarse mapping phase, which determines whether the receiver point 𝒘 and the sender point 𝒒 indeed satisfy dist(𝒒, 𝒘) ≤ 𝛿. This eliminates the false positives and yields the final results to the receiver. Recently, a growing body of literature [7, 11, 16, 17, 19, 38, 42, 45, 46, 50] has explored fuzzy PSI under 𝐿𝑝 distance for 𝑝 ∈ [1, ∞]. As detailed in Section 2, we categorize these prior works into lowdimensional and high-dimensional regimes, according to different techniques and designs. In general, these works typically begin by designing single-point fuzzy matching protocols, and then introduce fuzzy mapping techniques to compile fuzzy matching into multi-point fuzzy PSI. To achieve desirable asymptotic complexities, many recent constructions [11, 16, 45] rely on heavy cryptographic primitives, such as computation-intensive additively homomorphic encryption (AHE) or communication-intensive garbled circuits (GCs). Consequently, these protocols suffer from prohibitive concrete overhead. More recently, van Baarsen and Pu [46] propose the state-of-the-art fuzzy PSI scheme leveraging lightweight oblivious PRFs (OPRFs) to bypass these heavy primitives. Unfortunately, their protocols incur undesirable asymptotic complexities, scaling as O ((log 𝛿)𝑑 ) or O (𝛿) for the distance threshold 𝛿 and the dimension 𝑑. This may introduce severe bottlenecks in real-world applications requiring large distance thresholds. We refer to Table 1 for a comprehensive comparison of existing works. Motivated by these limitations, we pose the following question: Can we construct scalable fuzzy PSI protocols with both concrete and asymptotic efficiency guarantees?

Meng Hao et al.

assumptions, we achieve an overhead that scales linearly with the dimension 𝑑. We summarize our core contributions as follows. (1) Asymptotically efficient fuzzy matching. We design two asymptotically efficient fuzzy matching protocols. The first is built from our customized role-reversed OPRF and realizes 𝑂 (𝑑 log 𝛿) overhead, compared to 𝑂 ((log 𝛿)𝑑 ) in previous works. The second utilizes customized OT with 𝑂 (𝑑ℓ) overhead, which is particularly suitable for inputs with short bit length ℓ. (2) New framework of fuzzy PSI for low-dimensional sets. We propose a new fuzzy PSI framework on 𝐿𝑝 ∈ [1,∞] distance from a dual-layer hashing design, incorporating the spatial hashing and Cuckoo hashing. Our framework reduces fuzzy PSI to about 𝑚 fuzzy matching invocations, which outperforms previous constructions with 2𝑑 𝑛 invocations. Moreover, we introduce an input space reduction optimization while addressing subtle issues of false positives, which enables the use of our efficient OT-based fuzzy matching. (3) Improved fuzzy PSI for high-dimensional sets. We propose efficient fuzzy PSI protocols for high-dimensional sets on 𝐿𝑝 ∈ [1,∞] distance based on our OPRF- and OT-based fuzzy matching. Under the strong globally disjoint assumption on both parties’ sets, our protocols achieve an asymptotic complexity that is linear in the set sizes 𝑚, 𝑛 and the dimension 𝑑, and logarithmic in the distance threshold 𝛿. (4) Extensive experimental evaluations. We conduct extensive experiments under a wide range of parameter settings. The experimental results demonstrate that our protocols significantly outperform state-of-the-art constructions. In low-dimensional settings, for dimensions 𝑑 ranging from 2 to 8, our protocols achieve up to 145× faster computation and up to 20× lower communication cost. In high-dimensional settings, for dimensions 𝑑 ranging from 16 to 64, our protocols require up to 36× less running time and up to 54× less communication.

2

2.1 1.1

Our Contribution

We answer the above question affirmatively by proposing scalable fuzzy PSI for general 𝐿𝑝 ∈ [1,∞] distance over both low- and highdimensional sets from lightweight oblivious transfer (OT) and oblivious PRF (OPRF). For low-dimensional sets, our protocols achieve communication and computation complexities that scale linearly with the set sizes 𝑚, 𝑛 and logarithmically with the distance threshold 𝛿, along with an additional exponential factor on the dimension 𝑑. This factor also appears in previous works for low-dimensional (small 𝑑) settings. For high-dimensional sets, by leveraging stronger

Related Work

In this section, we discuss existing fuzzy PSI protocols for 𝐿𝑝 ∈ [1,∞] distance1 , as they align most closely with our setting. Because the protocol design of fuzzy PSI is largely dictated by the dimensionality of the input sets, we categorize state-of-the-art constructions into low-dimensional and high-dimensional regimes. A comprehensive comparison of these approaches alongside our work is summarized in Table 1.

Fuzzy PSI on Low-dimensional Sets

Previous fuzzy PSI works for low-dimensional sets instantiate fuzzy mapping using spatial hashing or its variants [19]. The high-level idea is to partition the space into hypercubes of small side length (also referred to as grid cells), so that the receiver only needs to determine whether any sender’s points lie in cells that are 𝛿-close to receiver’s points, without enumerating the entire space. Despite this efficiency improvement, spatial hashing–based solutions incur an overhead factor of 2𝑑 , which makes them practical primarily 1 There is also a substantial body of work on fuzzy PSI for Hamming distance [3, 8, 10, 15, 27, 44, 49], which we do not discuss in detail here.

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Table 1: Comparisons of existing fuzzy PSI protocols for 𝐿𝑝 ∈ [1,∞] distance, where the sender holds 𝑚 elements and the receiver holds 𝑛 elements in a 𝑑-dimensional space, and 𝛿 is the distance threshold. The protocols of [38, 46] and ours for low-dimensional sets essentially rely on the same assumption, as shown in Appendix A. For clarity, we unify it as the unique ball/center. Note that both [38] and our protocols for low-dimensional sets can be extended to arbitrary receiver sets, but introduce an additional multiplicative factor in complexity. Setting

Metric

Protocol [7] [45]

𝐿∞

Low Dimension

[11] [42] [38] [46] Ours [45] [11] [42]

𝐿𝑝

𝐿∞

High Dimension 𝐿𝑝

[38] [46] Ours [45] [16] [11] [50] [46] Ours [16] [11] [50] [46] Ours

Technique FSS AHE AHE AHE GC OPRF & OT OPRF OPRF & OT AHE AHE GC GC OPRF & OT OPRF OPRF & OT AHE AHE AHE so-OPRF OPRF OPRF AHE AHE so-OPRF OPRF OPRF & OT

Assumption

Communication

R, mini-univ. R, min > 2𝛿 R, min > 4𝛿 R, min > 4𝛿 S, disj. hash R ∧ S, unique ball/center R ∧ S, unique ball/center R ∧ S, unique ball/center R, min > 2𝛿 (𝑑 1/𝑝 + 1) R, min > 2𝛿 (𝑑 1/𝑝 + 1) S, disj. hash, 𝑝 = 1 S, disj. hash, 𝑝 = 2 R ∧ S, unique ball/center R ∧ S, unique ball/center R ∧ S, unique ball/center R, disj. proj. R ∧ S, disj. proj. R ∧ S, disj. proj. R ∧ S, 𝑠-separate R ∧ S, global disj. R ∧ S, global disj. R ∧ S, disj. proj. R ∧ S, disj. proj. R ∧ S, 𝑠-separate R ∧ S, global disj. R ∧ S, global disj.

𝑂 (𝑑𝑛 log 𝛿 + 𝑚2𝑑 (log 𝛿)𝑑 ) 𝑂 (𝛿𝑑𝑛 + 2𝑑 𝑚) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝑚) 𝑂 (𝑑 log 𝛿 (𝑛2𝑑 + 𝑚)) 𝑂 (𝑑 log 𝛿 (𝑛2𝑠 + 𝑚2𝑑 −𝑠 )) 𝑂 (𝑑 (𝛿𝑚 + 2𝑑 𝑛)) 𝑂 (𝑑 log 𝛿 (𝑚 + 2𝑑 𝑛)) 𝑂 (𝑑 (𝑚 log 𝛿 + 2𝑑 𝑛)) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝛿 𝑝 𝑚) 𝑂 (2𝑑 𝑝 (𝑑𝑛 log 𝛿 + 𝑚(log 𝛿)𝑑 ) + 𝑑𝑚 log 𝛿) 𝑂 (𝑑 log(𝑑𝛿)(𝑛2𝑑 + 𝑚2𝑑 −𝑠 )) 𝑂 (𝑑 log(𝑑𝛿) (𝑛2𝑑 + 𝑚2𝑑 −𝑠 ) + log3 (𝑑𝛿)𝑚2𝑑 −𝑠 ) 𝑂 (𝑑 (𝛿𝑚 + 2𝑑 𝑛)) 𝑂 (𝑑 (𝛿𝑚 + 2𝑑 𝑛) + 𝑝 (𝑚 + 2𝑑 𝑛) log 𝛿) 𝑂 ((𝑚𝑝 log 𝛿 + 2𝑑 𝑛)𝑑) 𝑂 ((𝛿𝑑) 2𝑛 + 𝑚) 𝑂 (𝛿𝑑 (𝑚 + 𝑛)) 𝑂 (𝑑 (𝑚 + 𝑛) log 𝛿) 𝑂 (𝛿 𝑠 𝑑𝑠 (𝑚 + 𝑛)) 𝑂 ((𝑚𝛿 + 𝑛)𝑑) 𝑂 ((𝑚 + 𝑛)𝑑 log 𝛿) 𝑂 (𝛿𝑑 (𝑚 + 𝑛) + 𝑝𝑚 log 𝛿) 𝑂 (𝑑𝑝𝑛 log 𝛿 + 𝑑𝑚 log 𝛿) 𝑂 (𝛿 𝑠 𝑑𝑠 (𝑚 + 𝑛) + 𝑝𝑚 log 𝛿) 𝑂 ((𝑚𝛿 + 𝑛)𝑑 + (𝑚 + 𝑛)𝑝 log 𝛿) 𝑂 ((𝑚 + 𝑛𝑝)𝑑 log 𝛿)

Computation Sender Receiver 𝑑 𝑑 𝑂 (𝑚2 (log 𝛿) ) 𝑂 ((log 𝛿)𝑑 𝑛 + 𝑑𝑚 log 𝛿) 𝑑 𝑂 (2 𝑑𝑚) 𝑂 (𝛿𝑑𝑛 + 2𝑑 𝑚) 𝑂 (𝑑𝑚) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝑚) 𝑂 (2𝑑 𝑑𝑛 log 𝛿 + 𝑚(log 𝛿)𝑑 ) 𝑂 (𝑑𝑚 log 𝛿) 𝑂 (2𝑑 −𝑠 𝑑𝑚 log 𝛿) 𝑂 (2𝑠 𝑑𝑛 log 𝛿) 𝑂 (𝛿𝑑𝑚) 𝑂 (𝑑2𝑑 𝑛 + 𝑚) 𝑂 (𝑑 (𝑚 + 2𝑑 𝑛) log 𝛿) 𝑂 (2𝑑 𝑛(𝑑 log 𝛿 + (log 𝛿)𝑑/2 )) 𝑂 (𝑚𝑑 log 𝛿) 𝑂 (𝑑 (𝑚 log 𝛿 + 2𝑑 𝑛)) 𝑂 ((𝑑 + 𝛿 𝑝 )𝑚) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝑚) 𝑂 (2𝑑 (𝑑𝑝𝑛 log 𝛿 + 𝑚(log 𝛿)𝑑 )) 𝑂 (𝑚(𝑑𝑝 log 𝛿 + 2𝑑 (log 𝛿)𝑑 )) 𝑂 (𝑑𝑚2𝑑 −𝑠 log(𝑑𝛿)) 𝑂 (𝑑𝑛2𝑠 log(𝑑𝛿)) 𝑂 (𝑚2𝑑 −𝑠 ((𝑑 log(𝑑𝛿) + log3 (𝑑𝛿))) 𝑂 (𝑛2𝑠 (𝑑 log(𝑑𝛿) + log3 (𝑑𝛿))) 𝑂 (𝛿𝑑𝑚) 𝑂 (𝑑2𝑑 𝑛 + 𝑚) 𝑂 (𝑑 (𝛿 + 2𝑑 𝑛) + 𝑝 (𝑚 + 2𝑑 𝑛) log 𝛿) 𝑂 (2𝑑 𝑛(𝑑 + 𝑝 log 𝛿)) 𝑂 (𝑚𝑝𝑑 log 𝛿) 𝑂 ((𝑚𝑝 log 𝛿 + 2𝑑 𝑛)𝑑) 𝑂 (𝑑 2𝑚) 𝑂 ((𝛿𝑑) 2𝑛 + 𝑚) 𝑂 (𝛿𝑑𝑚 + 𝑛) 𝑂 (𝛿𝑑𝑛 + 𝑚) 𝑂 (𝑑 (𝑚 + 𝑛) log 𝛿) 𝑂 (𝑑 (𝑚 + 𝑛) log 𝛿) 𝑑 𝑂 (𝛿 𝑠 𝑠 𝑚 + 𝑛) 𝑂 (𝛿 𝑠 𝑑𝑠 𝑛 + 𝑚) 𝑂 ((𝑚𝛿 + 𝑛)𝑑) 𝑂 (𝑛𝑑) 𝑂 ((𝑚 + 𝑛)𝑑 log 𝛿) 𝑂 (𝑛𝑑 log 𝛿 + 𝑚𝑑) 𝑂 (𝛿𝑑𝑚 + 𝑝𝑚 log 𝛿 + 𝑛) 𝑂 (𝛿𝑑𝑛 + 𝑝𝑚 log 𝛿) 𝑂 (𝑑𝑝𝑚 log 𝛿 + 𝑑𝑛 log 𝛿) 𝑂 (𝑑𝑝𝑛 log 𝛿 + 𝑑𝑚 log 𝛿) 𝑂 ((𝛿 𝑠 𝑑𝑠 + 𝑝 log 𝛿)𝑚 + 𝑛) 𝑂 (𝛿 𝑠 𝑑𝑠 𝑛 + 𝑝𝑚 log 𝛿) 𝑂 ((𝑚𝛿 + 𝑛)𝑑 + (𝑚 + 𝑛)𝑝 log 𝛿) 𝑂 (𝑛(𝑑 + 𝑝 log 𝛿)) 𝑂 ((𝑚 + 𝑛𝑝)𝑑 log 𝛿) 𝑂 (𝑛𝑝𝑑 log 𝛿 + 𝑚𝑑)

– R/S denotes that the set of receiver/sender satisfies the assumption, and R ∧ S indicates that both sets satisfy the assumption. – unique ball/center means in spatial hashing, each grid cell intersects with at most one ball and each grid cell contains at most one point, respectively. – mini-univ is short for mini-universe assumption, where every ball can be mapped to a distinct vertex of the space. – min > 𝑙 means that the minimum distance between any two elements of the set is greater than 𝑙 . – disj. hash is short for disjoint hash assumption, which means the spatial hashing scheme maps at most one point to every possible target grid cell. – disj. proj. is short for disjoint projection assumption, where there exists at least one dimension on which the projection of balls does not overlap. – global disj. is short for globally disjoint projection assumption, where for every dimension, the projection of balls does not overlap. – 𝑠 -separate means for every 𝑠 dimensions, there exists at least one dimension on which the projection of balls does not overlap.

for low-dimensional settings. We summarize these works below according to their underlying technical approaches. Function secret sharing (FSS). Garimella et al. [19] introduce a general structure-aware PSI framework that can be adapted to fuzzy PSI. The key technique is a customized fuzzy matching protocol built from FSS [5, 6, 21] for testing membership in 𝐿∞ balls. To extend this FSS-based fuzzy matching to fuzzy PSI, they assume that points in the receiver’s set are at least 2𝛿 apart in 𝐿∞ distance. Their communication overhead scales as 𝑂 ((2 log 𝛿)𝑑 ). However, the computation overhead incurs an additional factor of 𝑂 (𝛿 𝑑 ), since the receiver must traverse all points that are 𝛿-close to each receiver point. To reduce this computational overhead, Garimella et al. [17] propose an improved fuzzy matching protocol based on incremental FSS. The key idea is to traverse the prefix representation of the receiver’s 𝛿-radius ball, which can be represented using only (log 𝛿)𝑑 points. As a result, their fuzzy PSI achieves both computa
tional and communication overheads scaling as 𝑂 (2 log 𝛿)𝑑 . Bui et al. [7] further optimize the concrete efficiency by removing a hidden multiplicative factor proportional to the computational security parameter, while preserving the same asymptotic complexity.

However, the main limitation of FSS-based fuzzy PSI is the overhead factor of 𝑂 ((2 log 𝛿)𝑑 ), which becomes prohibitive for large distance thresholds. Moreover, these methods only support 𝐿∞ distance, due to the lack of efficient FSS-based constructions for fuzzy matching under general 𝐿𝑝 distance. Additively homomorphic encryption (AHE). To support general 𝐿𝑝 ∈ [1,∞] distance, van Baarsen and Pu [45] propose fuzzy matching protocols leveraging the linear homomorphism of AHE. Their construction incurs 𝑂 (𝑑𝛿) computational and communication overhead. To realize fuzzy PSI, they employ improved spatial hashing, with the assumption that the receiver’s points are at least 2𝛿 (𝑑 1/𝑝 + 1) apart for 𝐿𝑝 ∈ [1,∞] distance. Subsequently, Dang et al. [11] improve the fuzzy matching protocol by integrating prefix trie techniques, reducing communication to 𝑂 (log 𝛿) and computation to 𝑂 ((log 𝛿)𝑑 ). They adopt the same framework to implement fuzzy PSI for general 𝐿𝑝 distances. However, both of these fuzzy PSI methods suffer from high computational overhead, scaling as 𝑂 (𝑑𝛿) or 𝑂 ((log 𝛿)𝑑 ), and rely on expensive public-key primitives. Garbled circuits (GC). To avoid expensive public-key operations, Richardson et al. [42] leverage GC [48], which is built on

CCS ’26, November 15–19, 2026, The Hague, Netherlands

symmetric primitives, to implement fuzzy matching, and further propose a fuzzy PSI framework based on disjoint hashing, a generalization of spatial hashing. Their framework encodes messages from the GC-based fuzzy matching protocols in an oblivious key-value store [2, 18], which maps a hash identifier for each party’s point to the corresponding next GC message. The resulting fuzzy PSI protocols for 𝐿∞ distance achieve 𝑂 (𝑚2𝑑 −𝑠 + 𝑛2𝑠 )𝑑 log 𝛿 communication, where 𝑠 ∈ [0, 𝑑] is an integer parameter that can be freely chosen. However, relying on GCs results in poor concrete communication and computational efficiency for fuzzy PSI, as observed in [38]. Oblivious pseudo-random function (OPRF). Recently, some of the most efficient fuzzy PSI protocols [38, 46] have been constructed using lightweight OPRF techniques. Specifically, van Baarsen and Pu [46] propose OPRF-based fuzzy matching protocols that support general 𝐿𝑝 ∈ [1,∞] distance and further optimize them using prefix trie techniques. To realize fuzzy PSI with these OPRF-based fuzzy matching protocols, they employ spatial hashing and assume that both the sender’s and receiver’s points are slightly separated. That is the points of both the sender’s and receiver’s sets are 2𝛿𝑑 1/𝑝 or 2𝛿 (𝑑 1/𝑝 + 1) apart from each other. Despite these optimizations, the resulting fuzzy PSI still incurs overhead scaling as 𝑂 ((log 𝛿)𝑑/2 ) for 𝐿∞ distance and 𝑂 (𝛿) for 𝐿𝑝 distance. Concurrently, Piske et al. [38] propose fuzzy matching protocols based on OPRF and oblivious transfer (OT). Their core technique, distance-aware OT, is a variant of OT in which the choice bit depends on whether the sender’s and receiver’s inputs are close. To achieve fuzzy PSI, they employ spatial hashing, assuming that each grid cell contains at most one sender input. However, unlike other protocols with prefix trie techniques, their protocols incur linear complexity in the distance threshold 𝛿.

2.2

Fuzzy PSI on High-dimensional Sets

To make fuzzy PSI practical for high-dimensional sets, it is necessary to mitigate the exponential overhead regarding 𝑑. Several works have addressed this challenge, but they rely on some strong assumptions as discussed below. Similar to low-dimensional sets, we organize these works according to different technical approaches. Function secret sharing (FSS). To mitigate the 2𝑑 factor in the complexity, Garimella et al. [19] assume that the receiver’s 𝛿-radius balls are globally disjoint, meaning that the projections of all receiver balls do not overlap in any dimension. Under this assumption, they propose an FSS-based fuzzy PSI protocol that achieves communication complexity scaling to 𝑂 (𝑑 log 𝛿), but incurs a computational overhead of 𝑂 (𝛿 𝑑 ). Additively homomorphic encryption (AHE). Subsequently, van Baarsen and Pu [45] relax the globally disjoint assumption by introducing the existing disjoint assumption. That is, for each receiver’s ball, there exists at least one dimension on which its projection does not overlap with that of others. They propose a fuzzy matching protocol based on DDH and extend it to realize fuzzy PSI. However, their protocols’ complexity remains quadratic in 𝑑. Recently, Gao et al. [16] introduce fuzzy mapping, generalizing spatial hashing-based solutions, and construct fuzzy PSI for high-dimensional sets based on AHE and DDH. Their fuzzy PSI protocol requires that both parties satisfy the existing disjoint assumption and realizes communication and computation costs linear

Meng Hao et al.

Functionality F(ss)FMatch Parameters: Sender S and receiver R. Distance metric dist(·, ·) and threshold 𝛿. Functionality: (1) Wait for input 𝒒 ∈ Z𝑑2ℓ from S and 𝒘 ∈ Z𝑑2ℓ from R. (2) Compute 𝑧 := 1{dist(𝒒, 𝒘 ) ≤ 𝛿 } (3) FMatch: Output 𝑧 to R. (4) ssFMatch: Sample 𝑧 S , 𝑧 R ← F2 such that 𝑧 S ⊕ 𝑧 R = 𝑧. Output 𝑧 S to S and 𝑧 R to R.

Figure 1: Functionality of (secret-shared) fuzzy matching.

in 𝛿, 𝑑, 𝑚, 𝑛. Dang et al. [11] further optimize these protocols using prefix representations, reducing the dependence on 𝛿 to logarithmic. Despite these improvements, a key limitation of these works is poor concrete efficiency due to expensive public-key operations. Oblivious pseudo-random function (OPRF). To address the above efficiency issue, Zhang et al. [50] recently propose an intermediate assumption, which they call the 𝑠-separated set assumption. This assumption states that for every 𝑠 dimensions of each point, there exists at least one dimension on which its projection does not overlap with that of others. When 𝑠 = 1, this degenerates the globally disjoint assumption [19], and when 𝑠 = 𝑑, it corresponds to the existing disjoint assumption [45]. They construct fuzzy PSI using shared-output OPRF [1, 13], which rely on two-party computation to evaluate MPC-friendly low-degree PRF, introducing large communication and computation overhead. More recently, relying on the globally disjoint assumption on both parties, van Baarsen and Pu [46] propose the first fuzzy PSI protocol based solely on lightweight OPRF, achieving communication and computation costs that are linear in 𝛿, 𝑑, 𝑚, 𝑛.

3 Preliminaries 3.1 Notations We use 𝜅 and 𝜆 to denote the computational and statistical security parameters, respectively. The symbols 𝑚 and 𝑛 denote the set sizes of the sender and the receiver, respectively. Bold letters (e.g., 𝒒) represent input points with dimension 𝑑, and 𝑞𝑘 denotes the 𝑘th coordinate of 𝒒. For a positive integer 𝑎, [𝑎] denotes the set {1, . . . , 𝑎}. The notation 𝑠 ← 𝑆 indicates that 𝑠 is sampled uniformly at random from 𝑆. The indicator function 1{event} equals 1 if the event occurs and 0 otherwise.

3.2

Fuzzy Matching and Fuzzy PSI

We introduce the functionality of fuzzy matching and its secretshared variant in Figure 1 and that of fuzzy PSI in Figure 2 for some distance metric dist on 𝑑-dimensional space. Fuzzy matching can be viewed as a simplified single-point version of fuzzy PSI.

3.3

Prefix Representations of Intervals

We present the prefix trie technique [8, 11, 46] that succinctly and efficiently represents an integer interval. Theorem 3.1 ([46]). Given an integer interval [𝑞−𝛿, 𝑞+𝛿] ∈ Z2𝛿+1 2ℓ and a point 𝑤 ∈ Z2ℓ , there are two algorithms with 𝑢, 𝑢 ′ = 𝑂 (log 𝛿):

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Functionality FFPSI

Functionality FOPPRF

Parameters: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Distance metric dist(·, ·) and threshold 𝛿. Functionality: (1) Wait for input 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ Z𝑑2ℓ×𝑚 from S and 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ Z𝑑2ℓ×𝑛 from R. (2) Output 𝑍 := {𝒒 𝑗 | ∃𝑖 ∈ [𝑛], dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿 } to R.

Parameters: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Functionality: (1) Wait for input 𝐿 = { (𝑘 𝑗 , 𝑣 𝑗 ) } 𝑗 ∈ [𝑚] ⊆ Z2ℓ × F from S and 𝑄 = {𝑞𝑖 }𝑖 ∈ [𝑛] ⊆ Z2ℓ from R. (2) Sample a random function 𝐹 : Z2ℓ → F such that 𝐹 (𝑘 ) = 𝑣 for (𝑘, 𝑣) ∈ 𝐿. (3) For 𝑖 ∈ [𝑛], compute 𝑦𝑖 := 𝐹 (𝑞𝑖 ). (4) Output O 𝐹 to S and {𝑦𝑖 }𝑖 ∈ [𝑛] to R.

Figure 2: Functionality of fuzzy PSI. (1) PxTrie(𝑞 − 𝛿, 𝑞 + 𝛿) → {𝑞˜1, . . . , 𝑞˜𝑢 }: The PxTrie algorithm succinctly encodes the interval [𝑞 − 𝛿, 𝑞 + 𝛿] into 𝑢 prefix nodes {𝑞˜1, . . . , 𝑞˜𝑢 } ∈ Z𝑢2ℓ that cover the entire interval without overlap. Specifically, 𝑢 ≤ 2 + log 𝛿 when 𝛿 is a power of 2. (2) PxPath(𝑤, 𝛿) → {𝑤˜ 1, . . . , 𝑤˜ 𝑢 ′ }: The PxPath algorithm expands each query point 𝑤 ∈ Z2ℓ into a path of prefix nodes ′ {𝑤˜ 1, . . . , 𝑤˜ 𝑢 ′ } ∈ Z𝑢2ℓ , where 𝑢 ′ := ⌊log(2𝛿 + 1)⌋ + 1. Then, it holds that 𝑤˜ 𝑡 ∈ {𝑞˜1, . . . , 𝑞˜𝑢 } for some unique 𝑡 ∈ [𝑢 ′ ] if and only if 𝑤 ∈ [𝑞 − 𝛿, 𝑞 + 𝛿]. That means if 𝑤 ∈ [𝑞−𝛿, 𝑞+𝛿], there exists a unique 𝑡 ∈ [𝑢 ′ ] such that 𝑤˜ 𝑡 ∈ {𝑞˜1, . . . , 𝑞˜𝑢 }; otherwise, {𝑞˜𝑡 }𝑡 ∈ [𝑢 ] ∩ {𝑤˜ 𝑡 }𝑡 ∈ [𝑢 ′ ] = ∅. To simplify the exposition of security proofs, we establish the following three direct corollaries. Corollary 3.2. Given any two intervals [𝑞 −𝛿, 𝑞 +𝛿], [𝑞 ′ −𝛿, 𝑞 ′ + 𝛿] ∈ Z2𝛿+1 such that |𝑞 − 𝑞 ′ | > 2𝛿, it holds that PxTrie(𝑞 − 𝛿, 𝑞 + 2ℓ 𝛿) ∩ PxTrie(𝑞 ′ − 𝛿, 𝑞 ′ + 𝛿) = ∅. Proof. Suppose for contradiction there exists 𝑧 ∗ ∈ PxTrie(𝑞 − 𝛿, 𝑞 +𝛿) ∩PxTrie(𝑞 ′ −𝛿, 𝑞 ′ +𝛿). Let 𝑧 be any specific value covered by the prefix 𝑧 ∗ (e.g., the value obtained by setting all trailing wildcard bits to 0). This means 𝑧 ∈ [𝑞 −𝛿, 𝑞 +𝛿] ∩ [𝑞 ′ −𝛿, 𝑞 ′ +𝛿], which implies |𝑧 −𝑞| ≤ 𝛿 and |𝑧 −𝑞 ′ | ≤ 𝛿. This yields |𝑞 −𝑞 ′ | = |(𝑞 −𝑧) − (𝑞 ′ −𝑧)| ≤ |𝑞 − 𝑧| + |𝑞 ′ − 𝑧| ≤ 2𝛿. This contradicts the assumption |𝑞 − 𝑞 ′ | > 2𝛿. Therefore, the intersection is empty. □ Corollary 3.3. Given any two points 𝑤, 𝑤 ′ ∈ Z2ℓ such that |𝑤 − 𝑤 ′ | > 2𝛿, it holds that PxPath(𝑤, 𝛿) ∩ PxPath(𝑤 ′, 𝛿) = ∅. Proof. Suppose for contradiction there exists 𝑧 ∈ PxPath(𝑤, 𝛿)∩ PxPath(𝑤 ′, 𝛿). By Theorem 3.1, PxPath(·) outputs 𝑢 ′ prefixes with at most 𝑢 ′ − 1 trailing wildcards, where 𝑢 ′ = ⌊log(2𝛿 + 1)⌋ + 1. Since the shared prefix 𝑧 has at most 𝑢 ′ − 1 wildcards, this yields ′ |𝑤 −𝑤 ′ | ≤ 2𝑢 −1 −1 = 2 ⌊log(2𝛿+1) ⌋ −1 ≤ 2log(2𝛿+1) −1 = 2𝛿. This contradicts the assumption |𝑤 − 𝑤 ′ | > 2𝛿. Therefore, the intersection is empty. □ Corollary 3.4. Given any interval [𝑞 − 𝛿, 𝑞 + 𝛿] ∈ Z2𝛿+1 , for 2ℓ any two points 𝑤, 𝑤 ′ ∈ Z2ℓ such that |𝑤 − 𝑤 ′ | > 2𝛿, there exists at most one point 𝑣 ∈ {𝑤, 𝑤 ′ } such that PxTrie(𝑞 − 𝛿, 𝑞 + 𝛿) ∩ PxPath(𝑣, 𝛿) ≠ ∅. Proof. Suppose for contradiction that both intersections are non-empty. By Theorem 3.1, this implies 𝑤 ∈ [𝑞 − 𝛿, 𝑞 + 𝛿] and 𝑤 ′ ∈ [𝑞−𝛿, 𝑞+𝛿]. This contradicts the assumption that |𝑤 −𝑤 ′ | > 2𝛿. Therefore, at most one point 𝑣 ∈ {𝑤, 𝑤 ′ } can yield a non-empty intersection. □

Figure 3: Functionality of oblivious programmable PRF.

3.4

Spatial Hashing

To extend single-point fuzzy matching to multi-point fuzzy PSI, prior works [7, 11, 16, 19, 38, 42, 45, 46] partition the entire input space into smaller hypercubes with side length 2𝛿, also referred to as grid cells. This tiling ensures that each point needs to be matched only against points residing in a bounded number of cells, instead of the whole input space. We formally define this approach, known as spatial hashing, below. We first introduce the definition of a cell and its identifier. A cell is defined as a 𝐿∞ hypercube of side length 2𝛿. The function cell2𝛿 (·) maps a point 𝒒 to the identifier of the cell. The identifier of the cor𝑞 𝑞 responding cell C𝒒 := cell2𝛿 (𝒒) is given by (⌊ 2𝛿1 ⌋ · 2𝛿, . . . , ⌊ 2𝛿𝑑 ⌋ · 2𝛿). Spatial hashing consists of two algorithms: (1) cellhash(·): The function maps a point 𝒒 ∈ Z𝑑2ℓ into its unique identifier C𝒒 of the cell containing 𝒒. (2) ballhash(·): The function maps a point 𝒒 ∈ Z𝑑2ℓ into a set of identifiers {C𝒒,ℎ }ℎ∈ [2𝑑 ] of the 2𝑑 cells that intersect the 𝐿∞ ball of radius 𝛿 centered at 𝒒.

3.5

(Programmable) Oblivious PRF

An oblivious pseudorandom function (OPRF) is a two-party protocol in which the receiver inputs a batch2 of queries {𝑞𝑖 }𝑖 ∈ [𝑛] . The sender obtains a random function 𝐹 , while the receiver learns only the corresponding evaluations {𝐹 (𝑞𝑖 )}𝑖 ∈ [𝑛] . Programmable OPRF (OPPRF), introduced by Kolesnikov et al. [30], extends this functionality by allowing the sender to program the function 𝐹 at designated inputs: for each sender-chosen pair (𝑘 𝑗 , 𝑣 𝑗 ), the functionality enforces 𝐹 (𝑘 𝑗 ) = 𝑣 𝑗 , whereas all non-programmed inputs are mapped to random outputs. We present the functionality of OPPRF in Figure 3. The state-of-the-art OPPRF protocols [39, 43] are constructed by combining OPRF with oblivious key-value stores (OKVS) [18]. Our protocols directly use OPPRF as a fundamental building block, instead of OPRF.

3.6

Weak Labeled PSI

As illustrated in Figure 4, weak labeled PSI [46] is a two-party protocol, where the sender inputs {(𝑞 𝑗 , label 𝑗 )} 𝑗 ∈ [𝑚] and the receiver inputs 𝑊 = {𝑤𝑖 }𝑖 ∈ [𝑛] . The receiver learns {(𝑞 𝑗 , label 𝑗 )} for 𝑞 𝑗 ∈ 𝑊 . It differs from the standard notion of labeled PSI in that the functionality outputs the tuple of the intersection item and 2We note that our protocols invoke only multi-query OPRFs. For simplicity, we omit

the qualifier “multi-query” in the remainder of the paper.

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Meng Hao et al.

Functionality FwLPSI

Functionality FPerm

Parameters: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Functionality: (1) Wait for input { (𝑞 𝑗 , label 𝑗 ) } 𝑗 ∈ [𝑚] from S and 𝑊 = {𝑤𝑖 }𝑖 ∈ [𝑛] from R. (2) Output { (𝑞 𝑗 , label 𝑗 ) | 𝑗 ∈ [𝑚], 𝑞 𝑗 ∈ 𝑊 } to R.

Parameters: Sender S and receiver R. Input size 𝑛 Functionality: (1) Wait for input ( {𝑥𝑖S }𝑖 ∈ [𝑛] ∈ F𝑛 ) from S and ( {𝑥𝑖R }𝑖 ∈ [𝑛] ∈ F𝑛 ) from R. (2) Sample a random permutation 𝜋 . For 𝑖 ∈ [𝑛], compute 𝑦𝑖 := 𝑥 𝜋 (𝑖 ) , where 𝑥 𝜋 (𝑖 ) := 𝑥 𝜋S (𝑖 ) + 𝑥 𝜋R (𝑖 ) ∈ F. (3) Output 𝜋 to S and {𝑦𝑖 }𝑖 ∈ [𝑛] to R.

Figure 4: Functionality of weak labeled PSI. Figure 6: Functionality of oblivious permutation. Functionality F(ss)PEQT Parameters: Sender S and receiver R. Functionality: (1) Wait for input 𝑥 ∈ F2ℓ from S and 𝑦 ∈ F2ℓ from R. (2) Compute 𝑏 := 1{𝑥 = 𝑦 } ∈ F2 . (3) PEQT: Output 𝑏 to R. (4) ssPEQT: Sample 𝑏 S , 𝑏 R ← F2 such that 𝑏 S ⊕ 𝑏 R = 𝑏. Output 𝑏 S to S and 𝑏 R to R.

Figure 5: Functionality of (secret-shared) private equality test.

its corresponding label, instead of just the label. [46] presents an efficient protocol realizing weak labeled PSI from OPRF.

3.7

(Secret-shared) Private Equality Test

The functionality of the private equality test (PEQT) and its secretshared variant are given in Figure 5.

3.8

Cuckoo Hashing

Cuckoo hashing was introduced by Pagh and Rodler [31]. It maps 𝑚 items into a table 𝑇 with 𝑚 ′ = 𝜖𝑚 bins using 𝑘 hash functions 𝐻 1, . . . , 𝐻𝑘 . Cuckoo hashing ensures that each bin contains at most one item through the following procedure. For an item 𝑥, insert it into any empty bin among 𝑇 [𝐻 1 (𝑥)], . . . ,𝑇 [𝐻𝑘 (𝑥)]. If all such bins are occupied, randomly select one of the 𝑘 bins, evict the existing item 𝑦, and attempt to reinsert 𝑦 using the same set of hash functions. This process is repeated until all items are successfully placed. Recent works [37] empirically show that with appropriate parameters of 𝜖, 𝑘, Cuckoo hashing can achieve negligible failure probability.

3.9

Oblivious Permutation

The oblivious permutation functionality receives a secret-shared vector from the two parties. Then, the sender learns a random permutation, and the receiver obtains the permuted vector. The functionality is given in Figure 6. Recent works [9, 22, 32] provide efficient protocols for oblivious permutation and its variants.

4

Technical Overview

In this section, we first introduce efficient fuzzy matching protocols and then present a new framework to compile our single-point fuzzy matching to multi-point fuzzy PSI.

4.1

Asymptotically Efficient Fuzzy Matching

We propose two fuzzy matching protocols for 𝐿∞ distance based on OPRF and OT, respectively. The two protocols target different application scenarios, depending on the bit length of the input points. The extension to 𝐿𝑝 distance of OT-based fuzzy matching is provided in Appendix B.2. Construction from role-reversed oblivious PRF. Our first construction is based on programmable OPRF (OPPRF, see Section 3.5), and achieves 𝑂 (𝑑 log 𝛿) computational and communication overhead. This improves upon the state-of-the-art work [46], which also relies on OPPRF but incurs computational overhead 𝑂 (𝑑 log 𝛿 + (log 𝛿)𝑑/2 ). Our starting point is the OPPRF-based fuzzy matching protocol from [46]. Specifically, for each dimension 𝑘 ∈ [𝑑], the sender programs an OPPRF, which maps all points in the interval [𝑞𝑘 −𝛿, 𝑞𝑘 +𝛿] to the same random value 𝑟𝑘 . The receiver then obtains the OPPRF evaluation 𝑟ˆ𝑘 on input 𝑤𝑘 . Finally, the two parties privately check Í Í whether 𝑘 ∈ [𝑑 ] 𝑟𝑘 = 𝑘 ∈ [𝑑 ] 𝑟ˆ𝑘 . With appropriate parameters, this holds if and only if 𝑤𝑘 ∈ [𝑞𝑘 −𝛿, 𝑞𝑘 +𝛿] for all 𝑘 ∈ [𝑑]. This elegant protocol incurs an overhead of 𝑂 (𝑑𝛿). The work [46] further optimizes this protocol to achieve logarithmic dependence on 𝛿 using the prefix trie technique (see Section 3.3). This enables representing the interval [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿] with only 𝑢 = 𝑂 (log 𝛿) elements, hence reducing the number of points programmed by the sender in the OPPRF from 2𝛿 +1 to 𝑢. Nevertheless, as a trade-off, the receiver obtains 𝑢 ′ = 𝑂 (log 𝛿) OPPRF evaluations {𝑟ˆ𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] for each dimension 𝑘. As a result, the receiver has to compare all possible combinations Í Í of 𝑘 ∈ [𝑑 ] 𝑟ˆ𝑘,𝑡𝑘 for 𝑡𝑘 ∈ [𝑢 ′ ] with the sender’s 𝑘 ∈ [𝑑 ] 𝑟𝑘 . The optimization achieves 𝑂 (𝑑 log 𝛿) communication overhead; however, it unfortunately causes a computational overhead of 𝑂 ((log 𝛿)𝑑/2 ) even with additional optimizations. To address this problem, we propose a new fuzzy matching protocol based on two role-reversed OPPRF invocations. Specifically, our protocol incorporates prefix trie techniques and executes the first OPPRF like that of [46]. After the receiver obtains OPPRF evaluations {𝑟ˆ𝑘,1, . . . , 𝑟ˆ𝑘,𝑢 ′ } for each dimension 𝑘, the parties invoke a second OPPRF with reversed roles to compress these 𝑢 ′ evaluations into a single value. More concretely, for each dimension 𝑘 ∈ [𝑑], the receiver (as a sender S in this OPPRF) programs an OPPRF that maps these 𝑢 ′ points {𝑟ˆ𝑘,1, . . . , 𝑟ˆ𝑘,𝑢 ′ } to the same random value 𝑠ˆ𝑘 , while the sender (as a receiver R in this OPPRF) obtains the OPPRF evaluation 𝑠𝑘 on input 𝑟𝑘 . In Figure 7, we illustrate the two role-reversed invocations of OPPRF for clarity. As shown by our careful analysis in Section 5.1, this construction guarantees that

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

Sender ( {𝑞𝑞�𝑘𝑘,𝑡𝑡 }𝑡𝑡∈[𝑢𝑢] , 𝑟𝑟𝑘𝑘 )

role reverse

ℱOPPRF �𝑘𝑘,𝑡𝑡 }𝑡𝑡∈[𝑢𝑢′ ] Receiver {𝑤𝑤

CCS ’26, November 15–19, 2026, The Hague, Netherlands

𝑟𝑟𝑘𝑘

𝑠𝑠𝑘𝑘

ℱOPPRF {𝑟𝑟𝑘𝑘,𝑡𝑡 ̂ }𝑡𝑡∈[𝑢𝑢′ ]

( {𝑟𝑟𝑘𝑘,𝑡𝑡 ̂ }𝑡𝑡∈[𝑢𝑢′ ] , 𝑠𝑠̂𝑘𝑘 )

Figure 7: Fuzzy matching from role-reversed OPPRF.

𝑠𝑘 = 𝑠ˆ𝑘 if and only if 𝑤𝑘 ∈ [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿]. Finally, the parties Í Í privately check whether 𝑘 ∈ [𝑑 ] 𝑠𝑘 = 𝑘 ∈ [𝑑 ] 𝑠ˆ𝑘 . It is worth noting that, although our protocol requires two OPPRF invocations, it maintains 𝑂 (𝑑 log 𝛿) communication complexity (with a slightly larger constant factor) and significantly reduces the computational overhead from 𝑂 ((log 𝛿)𝑑/2 ) in [46] to 𝑂 (𝑑 log 𝛿). Construction from oblivious transfer. Our second construction is based on OT and incurs 𝑂 (𝑑ℓ) communication and computational overhead, where ℓ denotes the bit length of the input points. When ℓ = 𝑂 (log 𝛿), this construction achieves 𝑂 (𝑑 log 𝛿) overhead as our OPRF-based approach. Notably, the OT-based construction achieves smaller concrete communication costs, as it eliminates the hidden dependence on the statistical security parameter 𝜆 inherently required in OPRF-based constructions [46]. In particular, our OT-based construction leverages recent OT protocols for computing the most significant bit (MSB) and AND [26, 41]. Although technically straightforward and largely overlooked in recent works, this approach achieves highly competitive performance, particularly for small input domains. As demonstrated in our fuzzy PSI protocols for low-dimensional sets, we reduce fuzzy PSI to fuzzy mapping with a small input bit length, namely ℓ = 𝑂 (log 𝛿). This significantly reduces communication overhead compared to OPRFbased approaches due to eliminating the factor 𝜆, while incurring only 𝑂 (log log 𝛿) communication rounds.

4.2

New Framework for Fuzzy PSI

Building upon our single-point fuzzy matching, we now construct multi-point fuzzy PSI protocols. In this section, we focus exclusively on low-dimensional sets, deferring our high-dimensional constructions to Section 7 and Appendix C. To circumvent the prohibitive O (𝑚𝑛) quadratic overhead inherent to naive pairwise comparisons, we adopt spatial hashing (see Section 3.4) to partition the global 𝑑-dimensional input space into grid cells of side length 2𝛿. For the sender’s set, we assume each grid cell contains at most one point. This structural assumption exactly mirrors the setting in [38] and is strictly weaker than the constraints imposed by the majority of prior fuzzy PSI schemes [11, 16, 46, 50]. Furthermore, for clarity of exposition, the following protocols further assume that each grid cell intersects at most one 𝛿-radius ball centered at a receiver point. This constraint aligns with the protocols in [46] and the empirical evaluation framework utilized in [38]. We discuss the extension to arbitrary receiver sets, achieved by leveraging stateful spatial hashing [38, 42], in Section 6.2. New framework via dual-layer hashing. We present a new fuzzy PSI framework for generalized 𝐿𝑝 ∈ [1,∞] distance, driven by

𝒘2

𝒒1

𝒒2 𝒘1

𝒘2

𝒒1

𝒒2 𝒘1

Figure 8: Comparison of fuzzy matching invocations of prior works (left) and ours (right) represented by gray shaded cells.

a dual-layer hashing strategy that combines spatial hashing with Cuckoo hashing. The core innovation of our approach is an interactive fuzzy mapping phase, which filters the candidate space down to approximately 𝑚 pairs of points for the final fuzzy matching. This design substantially reduces the overhead of prior OPRF-based constructions [38, 46], which implicitly require 2𝑑 𝑛 fuzzy matching invocations. To understand this reduction, we first recall existing fuzzy mapping approaches based on spatial hashing. The sender applies a cellhash function to assign each of its points 𝒒 to a unique cell C𝒒 . Conversely, the receiver applies a ballhash function to associate each of its points 𝒘 with 2𝑑 distinct cells, {C𝒘,ℎ }ℎ∈ [2𝑑 ] , representing all cells intersected by the 𝛿-radius ball centered at 𝒘. To find matches, the receiver only needs to compare 𝒘 against sender points located in these 2𝑑 cells, since any sender point 𝒒 satisfying dist(𝒒, 𝒘) ≤ 𝛿 must reside in one of them. However, when scaled across all 𝑛 receiver points, this paradigm forces prior protocols to execute approximately O (2𝑑 𝑛) heavy fuzzy matching operations. Our key observation is that the vast majority of these 2𝑑 𝑛 receiver search cells are empty on the sender’s side, since there are at most 𝑚 cells in which the sender’s points lie. Consequently, the parties only need to perform fuzzy matching on the 𝑚 specific cells that actually contain the sender’s input points. This insight reduces the required number of fuzzy matching invocations from O (2𝑑 𝑛) to just O (𝑚) (as illustrated in Figure 8). To realize this efficiently, we draw inspiration from circuit-based PSI [24, 36, 43] and employ Cuckoo hashing (detailed in Section 3.8) over spatial hashing. Concretely, the sender uses Cuckoo hashing to map its 𝑚 cell-point tuples (C𝒒 , 𝒒) into a table of size O (𝑚), while the receiver applies simple hashing to its 2𝑑 𝑛 tuples (C𝒘,ℎ , 𝒘). Because both parties use identical hash functions, candidate pairs sharing the same cell identifier will collide in the same bin, isolating the valid candidates for fuzzy matching. To further minimize the number of fuzzy matching invocations per bin, our protocol integrates an OPPRF. Specifically, for each bin 𝑖, the receiver programs the OPPRF3 such that, for every tuple (C𝒘,ℎ , 𝒘) residing in that bin, the function maps the cell identifier C𝒘,ℎ to 𝒘 − 𝒓𝑖 , utilizing a single random mask 𝒓𝑖 for the entire bin. The sender then queries the OPPRF using its input cell C𝒒 . If a matching cell exists in bin 𝑖, the sender successfully learns 𝒘 − 𝒓𝑖 , 3 Our protocol actually performs a single OPPRF invocation over all bins jointly, instead

of an OPPRF instance per bin. This avoids the receiver from padding each bin with dummy items to hide the number of items per bin. Similar techniques have been adopted in circuit-based PSI [36, 39, 43].

CCS ’26, November 15–19, 2026, The Hague, Netherlands

while the receiver retains the mask 𝒓𝑖 . Together, these two values constitute secret shares of the receiver’s point 𝒘. As a result, each bin 𝑖 yields at most one candidate pair: the sender holds its plaintext point 𝒒, and the receiver’s point 𝒘 is secret-shared between them. Otherwise (no matched cells), according to the functionality of OPPRF, secret shares of a random value will be learned. The parties can then process these pairs independently across all bins using a secret-shared variant of our fuzzy matching protocol. OT-based fuzzy matching with reduced input domain. We instantiate the remaining fuzzy matching using our OT-based construction over a reduced input domain. Building on observations from prior work [7, 17, 19], spatial hashing effectively partitions the large input space into small cells. Specifically, for any sender point 𝒒, any potentially 𝛿-close receiver point must reside within the neighboring cells of 𝒒. Geometrically, this search space is bounded by a 𝑑-dimensional hypercube of side length 6𝛿 (as illustrated in Figure 12). By restricting operations to this reduced domain, as illustrated in Section 4.1, our OT-based fuzzy matching achieves substantially better concrete performance than the OPRF-based alternative. However, this domain reduction introduces a subtle risk of false positives. Consider a scenario where a cell contains a sender point 𝒒, but none of the receiver’s 𝛿-radius balls intersect this cell. As illustrated in the above dual-layer fuzzy mapping, the protocol might yield secret shares of a uniformly random point rather than a valid receiver point 𝒘. Because the input domain is now artificially small, the probability that this random point accidentally falls within a distance of 𝛿 from 𝒒 becomes non-negligible. This not only triggers false positives but also risks leaking information about the sender’s private input. To resolve this vulnerability, we integrate an additional consistency check. This mechanism explicitly verifies that the cell containing the sender’s point 𝒒 is identical to the cell intersected by the receiver’s point 𝒘. This structural guarantee ensures the receiver only learns 𝒒 if the fuzzy matching succeeds and both points legitimately map to the same cell. We defer the full technical details to Section 6. In summary, the concrete efficiency gains of our protocol over prior works stem from a synergistic combination of our dual-layer fuzzy PSI framework and our reduced-domain OT-based fuzzy matching. We emphasize that while our fuzzy PSI protocol still relies on OPPRF to process O (2𝑑 𝑛) items, it achieves substantially lower communication and computation overheads compared to prior OPPRF-based constructions [46]. Our construction requires only O (𝑚) OPPRF queries and transmits programmed payloads bounded by O (2𝑑 𝑛(𝑑 log 𝛿 + 𝜆)) bits due to reduced input domain. In contrast, prior works such as [46] suffer from a multiplicative factor 𝑂 (𝑑 log 𝛿 · 𝜆) in the 𝑂 (2𝑑 𝑛) invocations of fuzzy matching.

5 Fuzzy Matching 5.1 Fuzzy Matching for 𝐿∞ Distance from Oblivious PRF Our first construction is based on OPRF. As the design intuition has already been presented in Section 4.1, we describe the detailed protocol in Figure 9. The key technical contribution is two rolereversed invocations of OPPRF, which enable communication overhead 𝑂 (𝜆𝑑 log 𝛿) and computational overhead 𝑂 (𝑑 log 𝛿). We note

Meng Hao et al.

∞ Protocol Π𝐿FMatch-oprf

Parameter: Sender S and receiver R. Threshold 𝛿. ℓ1 := 𝜆+2 log(𝑢 ′ + 1) + log 𝑑 and ℓ2 := 𝜆. Input: S inputs 𝒒 = (𝑞 1 , . . . , 𝑞𝑑 ) ∈ Z𝑑2ℓ and R inputs 𝒘 = (𝑤1 , . . . , 𝑤𝑑 ) ∈ Z𝑑2ℓ . Protocol: (1) For 𝑘 ∈ [𝑑 ], S computes {𝑞˜𝑘,𝑡 }𝑡 ∈ [𝑢 ] := PxTrie(𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿 ), and R computes { 𝑤˜ 𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] := PxPath(𝑤𝑘 , 𝛿 ). (2) For 𝑘 ∈ [𝑑 ], S samples 𝑟𝑘 ← F2ℓ1 . S and R invoke functionality FOPPRF , where S inputs { (𝑘 ∥ 𝑞˜𝑘,𝑡 , 𝑟𝑘 ) }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ] and learns O 𝐹 , while R inputs {𝑘 ∥ 𝑤˜ 𝑘,𝑡 }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] and learns {𝑟ˆ𝑘,𝑡 = 𝐹 (𝑘 ∥ 𝑤˜ 𝑘,𝑡 ) }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] . (3) For 𝑘 ∈ [𝑑 ], R samples 𝑠ˆ𝑘 ← F2ℓ2 . S and R invoke functionality FOPPRF , where R as the sender inputs ′ { (𝑘 ∥ 𝑟ˆ𝑘,𝑡 , 𝑠ˆ𝑘 ) }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] and learns O 𝐹 , while S as the receiver inputs {𝑘 ∥𝑟𝑘 }𝑘 ∈ [𝑑 ] and learns {𝑠𝑘 = 𝐹 ′ (𝑘 ∥𝑟𝑘 ) }𝑘 ∈ [𝑑 ] . Í (4) S computes 𝑠 := 𝑘 ∈ [𝑑 ] 𝑠𝑘 ∈ F2ℓ2 , while R computes 𝑠ˆ := Í 𝑘 ∈ [𝑑 ] 𝑠ˆ𝑘 ∈ F2ℓ2 . (5) S and R invoke functionality FPEQT , where S inputs 𝑠, while R inputs 𝑠ˆ and learns 𝑧 ∈ F2 .

Figure 9: Fuzzy matching for 𝐿∞ distance from OPPRF

that the use of OPPRF in our protocol can be further optimized by invoking 𝑑 independent OPPRFs across different dimensions, each involving fewer programmed points and queries. This optimization is formalized as multi-batch OPPRF in [46], where batches of points are evaluated under multiple independent random functions. Extending the above protocol to support 𝐿𝑝 distance with the same asymptotic overhead remains challenging and is left as future work, since the use of prefix representations obscures precise distance information. We next state the security of the protocol and defer the detailed correctness and security analysis to Appendix E.1. The key point is to ensure that {𝑟ˆ𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] are different since they are the programmed points in the second OPPRF invocation, and that 𝑟𝑘 ∉ {𝑟ˆ𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] if 𝑤𝑘 ∉ [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿] to avoid false positives. ∞ Theorem 5.1. The protocol Π𝐿FMatch-oprf in Figure 9 realizes the functionality FFMatch for 𝐿∞ distance in Figure 1 against semi-honest adversaries in the (FOPPRF, FPEQT )-hybrid model.

5.2

Fuzzy Matching for 𝐿∞ Distance from Oblivious Transfer

Our second fuzzy matching construction is built on OT. To realize fuzzy matching, the goal is to securely evaluate the function 𝑧 = 1{dist∞ (𝒒, 𝒘) ≤ 𝛿 }, where dist∞ (𝒒, 𝒘) = max𝑘 ∈ [𝑑 ] |𝑞𝑘 − 𝑤𝑘 |. Rather than naively computing this function via absolute-value (ABS) and maximum (MAX) operations followed by a comparison with the threshold 𝛿, we optimize the protocol by directly checking whether |𝑞𝑘 −𝑤𝑘 | ≤ 𝛿 for every dimension 𝑘 ∈ [𝑑], and then aggregating the resulting comparison bits using AND operations. This approach reduces the overhead: the naive method requires 2𝑑 MSB operations and 2𝑑 Multiplexer operations to realize the ABS and MAX functionalities, whereas our optimized protocol only incurs 2𝑑 MSB operations together with lightweight AND operations.

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

CCS ’26, November 15–19, 2026, The Hague, Netherlands

∞ Protocol Π𝐿FMatch-ot

Protocol Π FPSI-low

Parameter: Sender S and receiver R. Threshold 𝛿. Input: S inputs 𝒒 = (𝑞 1 , . . . , 𝑞𝑑 ) ∈ Z𝑑2ℓ and R inputs 𝒘 = (𝑤1 , . . . , 𝑤𝑑 ) ∈ Z𝑑2ℓ . Protocol: (1) For 𝑘 ∈ [𝑑 ], S and R compute [𝑡𝑘 ] ℓ := 𝑞𝑘 − 𝑤𝑘 . (2) For 𝑘 ∈ [𝑑 ], S and R invoke functionality FMSB with input (𝛿 − [𝑡𝑘 ] ℓ ) and learn [𝑎𝑘 ] 1 . (3) For 𝑘 ∈ [𝑑 ], S and R invoke functionality FMSB with input (𝛿 + [𝑡𝑘 ] ℓ ) and learn [𝑏𝑘 ] 1 . (4) S and R invoke functionality FAND with input (1 ⊕ [𝑎 1 ] 1 , . . . , 1 ⊕ [𝑎𝑑 ] 1 , 1 ⊕ [𝑏 1 ] 1 , . . . , 1 ⊕ [𝑏𝑑 ] 1 ) and learn [𝑧 ] 1 . (5) S sends [𝑧 ] 1S to R, who constructs 𝑧 := [𝑧 ] 1S + [𝑧 ] 1R ∈ Z2 .

Parameter: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Table size 𝑚 ′ of Cuckoo hash with three hash functions 𝐻 1 , 𝐻 2 , 𝐻 3 : {0, 1} ∗ → [𝑚 ′ ]. Threshold 𝛿. ℓ1 := 𝜆 + log 𝑚 ′ . ℓ2 := ⌈log(6𝛿 ) ⌉ + 2 for 𝐿∞ distance; ℓ2 := ⌈log 𝑑 (6𝛿 ) ⌉ + 1 for 𝐿1 distance; ℓ2 := ⌈log(𝑑 (3𝛿 ) 2 ) ⌉ for 𝐿2 distance. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ Z𝑑2ℓ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ Z𝑑2ℓ×𝑛 . Protocol: (1) For 𝑗 ∈ [𝑚], S computes C𝒒 𝑗 := cellhash2𝛿 (𝒒 𝑗 ). For 𝑖 ∈ [𝑛], R computes { C𝒘𝑖 ,ℎ }ℎ∈ [2𝑑 ] := ballhash2𝛿 (𝒘𝑖 ). (2) S maps { ( C𝒒 𝑗 , 𝒒 𝑗 ) } 𝑗 ∈ [𝑚] into a Cuckoo hash table 𝑇𝑞 of 𝑚 ′ bins such that for any ( C𝒒 𝑗 , 𝒒 𝑗 ), there exists a 𝜏 ∈ [3] satisfying 𝑇𝑞 [𝐻𝜏 ( C𝒒 𝑗 ) ] = ( C𝒒 𝑗 ∥𝜏, 𝒒 𝑗 ). (3) R maps { ( C𝒘𝑖 ,ℎ , 𝒘𝑖 ) }𝑖 ∈ [𝑛],ℎ∈ [2𝑑 ] into a simple hash table 𝑇𝑤 of 𝑚 ′ bins, such that for any ( C𝒘𝑖 ,ℎ , 𝒘𝑖 ) and all 𝜏 ∈ [3], it holds that ( C𝒘𝑖 ,ℎ ∥𝜏, 𝒘𝑖 ) ∈ 𝑇𝑤 [𝐻𝜏 ( C𝒘𝑖 ,ℎ ) ]. (4) For 𝑗 ∈ [𝑚 ′ ], R samples 𝑠 𝑗 ← F2ℓ1 , 𝒓 𝑗 ← Z𝑑ℓ2 , and de2 fines 𝐿 𝑗 := { C𝒘 ∥𝜏, 𝑠 𝑗 ∥ (shift ⌈log 6𝛿⌉ (𝒘, C𝒘 − 2𝛿 ) − 𝒓 𝑗 mod 2ℓ2 ) } (C𝒘 ∥𝜏,𝒘) ∈𝑇𝑤 [ 𝑗 ] . (5) S and R invoke functionality FOPPRF , where R as the sender inputs {𝐿 𝑗 } 𝑗 ∈ [𝑚 ′ ] and learns O 𝐹 , while S as the receiver inputs { C𝒒 ∥𝜏 } (C𝒒 ∥𝜏,𝒒) ∈𝑇𝑞 and learns {𝑠ˆ𝑗 ∥ 𝒓ˆ 𝑗 } 𝑗 ∈ [𝑚 ′ ] . (6) For 𝑗 ∈ [𝑚 ′ ], S and R invoke functionality FssFMatch , where S inputs shift ⌈log 6𝛿⌉ (𝒒, C𝒒 − 2𝛿 ) − 𝒓ˆ 𝑗 mod 2ℓ2 such that 𝑇𝑞 [ 𝑗 ] = ( C𝒒 ∥𝜏, 𝒒) and R inputs 𝒓 𝑗 , and S and R learn 𝜈𝑗S ∈ F2 and 𝜈𝑗R ∈ F2 , respectively. (7) For 𝑗 ∈ [𝑚 ′ ], S and R invoke functionality FssPEQT , where S inputs 𝑠ˆ𝑗 and R inputs 𝑠 𝑗 , and learn 𝜇 S𝑗 ∈ F2 and 𝜇 R𝑗 ∈ F2 , respectively. (8) For 𝑗 ∈ [𝑚 ′ ], S and R input (𝜈𝑗S , 𝜇 S𝑗 ) and (𝜈𝑗R , 𝜇 R𝑗 ) to func-

Figure 10: Fuzzy matching for 𝐿∞ distance from OT

Our protocol for 𝐿∞ distance is presented in Figure 10. For simplicity, we use [𝑥] ℓ to denote the parties’ secret shares [𝑥] ℓS and [𝑥] ℓR of 𝑥 ∈ Z2ℓ . Specifically, our protocol relies on efficient and customized OT-based protocols for computing MSB and AND operations [26, 40, 41]. We describe the functionalities required for OT-based fuzzy matching and summarize the corresponding communication overhead in Appendix B.1. Overall, our protocol incurs 𝑂 (𝑑ℓ) computational and communication overhead. We extend OT-based fuzzy matching to arbitrary 𝐿𝑝 distance in Appendix B.2. Besides, OT-based fuzzy matching protocols are readily extended to realize the secret-shared fuzzy matching functionality in Figure 1 by omitting the last reconstruction step. We next state the security of the protocol and defer the detailed correctness and security analysis to Appendix E.2. ∞ Theorem 5.2. The protocol Π𝐿FMatch-ot in Figure 10 realizes the functionality FFMatch for 𝐿∞ distance in Figure 1 against semi-honest adversaries in the (FMSB, FAND )-hybrid model.

6 Fuzzy PSI over Low-dimensional Sets 6.1 Constructions We present our fuzzy PSI protocol for 𝐿𝑝 ∈ [1,∞] distance over lowdimensional sets in Figure 11. The protocol relies on assumptions on both the sender’s and receiver’s sets, which are consistent with those in [46] and the evaluation setup of [11]. That is, for the sender’s set, each grid cell contains at most one sender’s point; for the receiver’s set, each grid cell intersects with at most one 𝛿-radius ball centered at a receiver point. We discuss how to extend to arbitrary receiver sets in Section 6.2. Since the protocol intuition has already been presented in Section 4, we focus here on providing additional details of the domainreduction optimization used when invoking fuzzy matching. Reducing input domain of fuzzy matching. For a sender point 𝒒, any receiver point that is potentially 𝛿-close to 𝒒 must lie in one of the neighboring grid cells of 𝒒. Formally, the neighboring cells of 𝒒 are defined as {(C𝒒,1 + 𝑡 1, . . . , C𝒒,𝑑 + 𝑡𝑑 )}𝑡𝑖 ∈ { −1,0,1} , which collectively form a 𝑑-dimensional hypercube with side length 6𝛿. This significantly reduces the effective input domain for fuzzy matching. To execute fuzzy matching over this reduced domain, we

𝐿𝑝 ∈ [1,∞]

tionality FAND and learn 𝑏 S𝑗 and 𝑏 R𝑗 , respectively. (9) S and R invoke functionality FPerm , where S inputs {𝑏 S𝑗 } 𝑗 ∈ [𝑚 ′ ] and R inputs {𝑏 R𝑗 } 𝑗 ∈ [𝑚 ′ ] . S learns 𝜋 and R learns {𝑏ˆ 𝑗 } 𝑗 ∈ [𝑚 ′ ] such that 𝑏 S ⊕ 𝑏R = 𝑏ˆ 𝑗 for each 𝜋 (𝑗)

𝜋 (𝑗)

𝑗 ∈ [𝑚 ′ ]. (10) For 𝑗 ∈ [𝑚 ′ ], S and R invoke functionality FOT , where S inputs (⊥, 𝒒), where ( C𝒒 | |𝜏, 𝒒) = 𝑇𝑞 [𝜋 ( 𝑗 ) ], and R inputs 𝑏ˆ 𝑗 and receives 𝑧 𝑗 . (11) R outputs 𝑍 := {𝑧 𝑗 | 𝑧 𝑗 ≠ ⊥, 𝑗 ∈ [𝑚 ′ ] }.

Figure 11: Protocol of fuzzy PSI for 𝐿𝑝 ∈ [1,∞] distance over low dimensional sets

define a shift-and-truncate operation as follows: shiftℓ (𝒒, 𝒐) := (𝒒 − 𝒐) mod 2ℓ , where 𝒐 denotes the shift origin, and ℓ is the required bit length to represent points in the reduced domain. In our protocol, for each sender point 𝒒, the shift origin 𝒐 is chosen as the lower-left corner of the neighboring cells of 𝒒, which can be formally expressed as C𝒒 − 2𝛿. Figure 12 provides an illustrative example. We note that, for a receiver point 𝒘, the shift origin is determined by the cell intersected by the 𝛿-radius ball centered at 𝒘, rather than by the cell containing 𝒘 itself.

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Meng Hao et al.

Ball centered at 𝒘

∞ Protocol Π𝐿FPSI-high

Parameter: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Threshold 𝛿. Bit lengths ℓ1 := 𝜆 + 2 log(𝑚 + 𝑛𝑢 ′ ) + log 𝑑, ℓ2 := 𝜆 + log 𝑚 + log 𝑛. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ Z𝑑2ℓ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ Z𝑑2ℓ×𝑛 . Protocol: (1) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], S computes {𝑞˜ 𝑗,𝑘,𝑡 }𝑡 ∈ [𝑢 ] := PxTrie(𝑞 𝑗,𝑘 − 𝛿, 𝑞 𝑗,𝑘 + 𝛿 ). (2) For 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑 ], R computes { 𝑤˜ 𝑖,𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] := PxPath(𝑤𝑖,𝑘 , 𝛿 ). (3) S samples {𝑟 𝑗,𝑘 } ← F2ℓ1 for 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ]. S and R invoke functionality FOPPRF , where S inputs { (𝑘 ∥ 𝑞˜ 𝑗,𝑘,𝑡 , 𝑟 𝑗,𝑘 ) } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ] and learns O 𝐹 , while R inputs {𝑘 ∥ 𝑤˜ 𝑖,𝑘,𝑡 }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] and learns {𝑟ˆ𝑖,𝑘,𝑡 = 𝐹 (𝑘 ∥ 𝑤˜ 𝑖,𝑘,𝑡 ) }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] . (4) R samples 𝑠ˆ𝑖,𝑘 ← F2ℓ2 for 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑 ]. S and R invoke functionality FOPPRF , where R as the sender inputs ′ { (𝑘 ∥ 𝑟ˆ𝑖,𝑘,𝑡 , 𝑠ˆ𝑖,𝑘 ) }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] and learns O 𝐹 , while S as the receiver inputs {𝑘 ∥𝑟 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] and learns {𝑠 𝑗,𝑘 := 𝐹 ′ (𝑘 ∥𝑟 𝑗,𝑘 ) } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] . Í (5) For 𝑗 ∈ [𝑚], S computes 𝑠 𝑗 := 𝑘 ∈ [𝑑 ] 𝑠 𝑗,𝑘 . For 𝑖 ∈ [𝑛], R Í computes 𝑠ˆ𝑖 := 𝑘 ∈ [𝑑 ] 𝑠ˆ𝑖,𝑘 . (6) S and R invoke functionality FwLPSI , where S inputs { (𝑠 𝑗 , 𝒒 𝑗 ) } 𝑗 ∈ [𝑚] , while R inputs {𝑠ˆ𝑖 }𝑖 ∈ [𝑛] and learns 𝐼 . (7) R outputs 𝑍 := {𝒛 | (𝑏, 𝒛 ) ∈ 𝐼 }.

𝒘 𝒒

6𝛿 Origin

Figure 12: Illustration of reduced input domain after shifting Addressing false positives caused by small input domain. Although the above domain-reduction technique significantly reduces the overhead of fuzzy matching, as discussed in Section 4.2, it introduces false positives. In particular, after executing our OPPRFbased fuzzy mapping, the produced pair of points may consist of a sender point 𝒒 and a uniformly random point, rather than a valid receiver point 𝒘. Because the input domain is small, the probability that these two points are 𝛿-close is non-negligible, which may incorrectly reveal 𝒒 to the receiver. To mitigate this issue, the receiver appends an additional random value 𝑠 to the output of each programmed point in the OPPRF. Consequently, the sender obtains the same value 𝑠 if and only if both parties’ inputs correspond to the same cell identifier. We then perform an additional equality test in conjunction with fuzzy matching, which verifies whether the cell containing 𝒒 is identical to the cell intersected by 𝒘. This ensures that the receiver learns 𝒒 only when the fuzzy matching succeeds and the two points are associated with the same cell. Besides, the ordering of Cuckoo hashing leaks additional information about the sender’s entire set. To prevent the leakage, we adopt an oblivious permutation on the fuzzy matching results. The security of the protocol is shown as follows, and we defer the detailed correctness and security analysis to Appendix E.4.

Figure 13: Protocol of fuzzy PSI for 𝐿∞ distance over high dimensional sets

sender point 𝒒, we enumerate all possible matching cell identifiers as cellhash(𝒒, 𝜌) = {C𝒒 ∥ℎ}ℎ∈ [𝜌 ] . The remainder of the fuzzy PSI protocol remains identical to that shown in Figure 11. As in [38], our original protocol assumes 𝜌 = 1. When 𝜌 > 1, the complexity of our protocol increases by an additional multiplicative factor of 𝜌. Therefore, our construction supports fuzzy PSI for arbitrary receiver sets, requiring only the unique cell assumption on the sender’s set.

𝐿

𝑝 ∈ [1,∞] Theorem 6.1. The protocol ΠFPSI-low in Figure 11 realizes the functionality FFPSI for 𝐿𝑝 ∈ [1,∞] distance in Figure 2 against semi-honest adversaries in the (FOPPRF, FssFMatch, FssPEQT, FPerm, FAND, FOT )-hybrid model, if the sender’s (resp. receiver’s) set satisfies the unique center (resp. ball) assumption.

6.2

Extension to Arbitrary Receiver’s Set

Similar to [38], we can extend our protocols to support arbitrary receiver set distributions without imposing any structural assumptions. To this end, we define a density parameter 𝜌, which denotes the maximum number of receiver balls that intersect the same cell. We then adapt the spatial hashing scheme so that each receiver point is assigned a unique cell identifier. Specifically, we append a counter to the original cell identifier for each receiver ball. Formally, we redefine ballhash(𝒘, 𝜌) = {C𝒘,ℎ ∥𝐷 [C𝒘,ℎ ] + +}ℎ∈ [2𝑑 ] , where 𝐷 is a dictionary initialized as 𝐷 [C] := 1 for every cell identifier C. This ensures that even when multiple receiver balls map to the same cell, their identifiers remain unique. Correspondingly, for each

7

Fuzzy PSI over High-dimensional Sets

In this section, we present efficient fuzzy PSI protocols tailored for high-dimensional sets. In this setting, the protocols introduced in Section 6 suffer from an exponential 2𝑑 blowup in overhead, which is a fundamental bottleneck inherent to almost all spatial hashingbased approaches [7, 17, 19, 38, 42, 45, 46]. To bypass this curse of dimensionality, we leverage the globally disjoint assumption, previously adopted in [19, 46]. That is, the projections of the sender’s and receiver’s balls are globally disjoint in every dimension. While our protocols achieve desirable O ((𝑚 + 𝑛)𝑑 log 𝛿) computation and communication complexity, we acknowledge that this assumption enforces a strong structural constraint and is not entirely realistic. We formally present the globally disjoint assumption as follows. Definition 7.1 (Globally Disjoint Assumption [19, 46]). A set of 𝑑-dimensional balls of radius 𝛿 with centers 𝒒 1, . . . , 𝒒𝑚 is globally disjoint if, for each dimension 𝑘 ∈ [𝑑], the projections [𝑞 𝑗,𝑘 − 𝛿, 𝑞 𝑗,𝑘 + 𝛿] are disjoint for all 𝑗 ∈ [𝑚].

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

𝐿𝑝

Protocol ΠFPSI-high Parameter: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Threshold 𝛿. Table size 𝑛 ′ of Cuckoo hash with three hash functions 𝐻 1 , 𝐻 2 , 𝐻 3 : {0, 1} ∗ → [𝑛 ′ ]. Bit length ℓ ′ := 𝜆 + 𝑝 log 𝛿 + log 𝑛 ′ . Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ Z𝑑2ℓ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ Z𝑑2ℓ×𝑛 . Protocol: ∞ (1) S and R execute the steps 1-5 of protocol Π𝐿FPSI-high , and learn {id𝒒 𝑗 } 𝑗 ∈ [𝑚] and {id𝒘𝑖 }𝑖 ∈ [𝑛] , respectively. (2) S maps { (id𝒒 𝑗 , 𝒒 𝑗 ) } 𝑗 ∈ [𝑚] into a simple hash table 𝑇𝑞 of 𝑛 ′ bins, such that for any (id𝒒 𝑗 , 𝒒 𝑗 ) and all 𝜏 ∈ [3], it holds that (id𝒒 𝑗 ∥𝜏, 𝒒 𝑗 ) ∈ 𝑇𝑞 [𝐻𝜏 (id𝒒 𝑗 ) ]. (3) R maps { (id𝒘𝑖 , 𝒘𝑖 ) }𝑖 ∈ [𝑛] into a Cuckoo hash table 𝑇𝑤 of 𝑛 ′ bins such that for any (id𝒘𝑖 , 𝒘𝑖 ), there exists 𝜏 ∈ [3] satisfying 𝑇𝑤 [𝐻𝜏 (id𝒘𝑖 ) ] = (id𝒘𝑖 ∥𝜏, 𝒘𝑖 ). (4) S samples {𝒈𝑖 }𝑖 ∈ [𝑛 ′ ] ← Z𝑑ℓ ′ . For 𝑖 ∈ [𝑛 ′ ], S defines 𝐿𝑖 := 2 ′ mod 2ℓ } for all (id

{id𝒒 ∥𝜏, 𝒒 − 𝒈𝑖 𝒒 ∥𝜏, 𝒒) ∈ 𝑇𝑞 [𝑖 ]. (5) S and R invoke functionality FOPPRF , where S inputs {𝐿𝑖 }𝑖 ∈ [𝑛 ′ ] and learns O𝐺 , while R inputs {id𝒘 ∥𝜏 } (id𝒘 ∥𝜏,𝒘) ∈𝑇𝑤 and learns { 𝒈ˆ𝑖 := 𝐺 (id𝒘 ∥𝜏 ) }𝑖 ∈ [𝑛 ′ ] . (6) For 𝑖 ∈ [𝑛 ′ ], S and R invoke functionality FFMatch , where ′ S inputs 𝒈𝑖 and R inputs 𝒘 − 𝒈ˆ𝑖 mod 2ℓ such that 𝑇𝑤 [𝑖 ] = (id𝒘 ∥𝜏, 𝒘 ) and learns 𝑏𝑖 ∈ F2 . (7) For 𝑖 ∈ [𝑛 ′ ], S and R invoke functionality FOT , where S inputs (⊥, 𝒈𝑖 ), and R inputs 𝑏𝑖 and receives 𝒛𝑖 . (8) R outputs 𝑍 := {𝒛𝑖 + 𝒈ˆ𝑖 | 𝑧𝑖 ≠ ⊥, 𝑖 ∈ [𝑛 ′ ] }.

Figure 14: Protocol of fuzzy PSI for 𝐿𝑝 distance over high dimensional sets

Construction for 𝐿∞ distance. We compile our OPRF-based fuzzy matching protocol to construct fuzzy PSI for 𝐿∞ distance. We do not adopt our OT-based construction, since without spatial hashing it does not admit a sufficiently reduced input domain, leading to large overhead, especially for inputs with large bit length. The idea is that since both parties’ sets are globally disjoint, fuzzy PSI protocols can be constructed by using multiple invocations of disjoint OPRF-based fuzzy matching. We present here the protocol in Figure 13, and defer the detailed description to Appendix C. The security is shown in the following, and its proof is deferred to Appendix E.5. ∞ Theorem 7.2. The protocol Π𝐿FPSI-high in Figure 13 realizes the functionality FFPSI for 𝐿∞ distance in Figure 2 against semi-honest adversaries in the (FOPPRF, FwLPSI )-hybrid model if both parties’ sets satisfy the globally disjoint assumption.

Construction for 𝐿𝑝 Distance. We further present the fuzzy PSI protocol on high-dimensional sets for 𝐿𝑝 distance based on both OPRF- and OT-based fuzzy matching. Our core insight is that the 𝐿∞ protocol described above inherently generates unique identifiers prior to its final output, specifically, 𝑠 𝑗 for each sender point 𝒒 𝑗 and 𝑠ˆ𝑖 for each receiver point 𝒘𝑖 . For clarity, we relabel these intermediate values as id𝒒 𝑗 and id𝒘𝑖 . By design, a collision id𝒒 𝑗 = id𝒘𝑖 occurs, if and only if dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. Because the 𝐿∞ ball strictly bounds the 𝐿𝑝 ball, these identifiers serve as an effective coarse filter. The parties only need to perform the rigorous

CCS ’26, November 15–19, 2026, The Hague, Netherlands

dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿 check on candidate pairs that share an identical identifier. To execute this efficiently, we repurpose the Cuckoo hashing-based design from our low-dimensional protocol. However, instead of using spatial grid cells, we use the above intermediate values from the 𝐿∞ protocol in Figure 13 as identifiers. The formal protocol is presented in Figure 14, and additional descriptions are deferred to Appendix C. The security analysis is shown in the following, and its proof is deferred to Appendix E.6. 𝑝 Theorem 7.3. The protocol ΠFPSI-high in Figure 14 realizes the functionality FFPSI for 𝐿𝑝 distance in Figure 2 against semi-honest adversaries in the (FOPPRF, FFMatch, FOT )-hybrid model if both parties’ sets satisfy the globally disjoint assumption.

𝐿

8

Evaluation

We provide the full-fledged implementation of our protocols, and our code is available at https://github.com/Th0masAndy/ScalableFPSI and https://doi.org/10.5281/zenodo.20607518. We conduct our evaluation on a single server, equipped with two AMD EPYC 9554 processors and 512 GB of RAM. The sender and receiver are emulated as two separate threads within a single process. Each experiment is repeated ten times, and we report the average values. We set the computational security parameter to 𝜅 = 128 and the statistical security parameter to 𝜆 = 40. Network conditions are simulated using the Linux tc command, configured with a bandwidth of 10 Gbps and a latency of 0.02 ms, following recent works [7, 38, 45]. Implementation details. We provide the implementation details as follows. For OPPRF, we adopt the implementation from [39], which includes the classic construction based on OKVS and VOLEOPRF. For OT, we use silent OT from [33]. For MSB, we build on the implementation of [26], replacing their OT component with [33]. All hash functions are instantiated using BLAKE3. For cuckoo hashing parameters, we use 3 hash functions and no stash. Comparison baselines. We compare our protocols with the state-of-the-art fuzzy PSI schemes [38, 46], as their set assumptions align with ours, and all these protocols rely on OPRF (and OT). While [38] theoretically supports arbitrary receiver sets, their experimental evaluation adopts the same assumptions as ours and as in [46]. Since [46] does not provide an implementation, for a fair comparison, we implement their constructions with prefix-trie optimizations using the same components as in our protocols. We also incorporate their optimization for solving Knapsack problem [25], which is required in their protocols for 𝐿∞ distances to reduce computation overhead.

8.1

Performance for Low-dimensional Sets

We evaluate our protocols on low-dimensional sets under 𝐿∞ , 𝐿1 , and 𝐿2 distances, and compare them with the state-of-the-art protocols in [38, 46]. The results are reported in Tables 2, 4, and 5. Since [38] supports only 8-bit inputs, we do not report its performance for 𝛿 = 1024. Results of 𝐿∞ distance. As shown in Table 2, our protocol for 𝐿∞ distance demonstrates a significant advantage over [38, 46], especially for relatively large parameter settings. For example, when 𝑚 = 𝑛 = 216 and 𝑑 = 8, our protocol is 16∼147× faster than [46]

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Meng Hao et al.

Table 2: Comparisons of fuzzy PSI over low-dimensional sets for 𝐿∞ distance. "*" indicates unsupported or no implementation for the specific parameter setting. "—" indicates out of memory or too long running time. The best result is marked in blue. Set size 𝑚 =𝑛

Dim. 𝑑 2

212

4

8

2

216

4

8

2

218

4

8

Protocol van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours

Threshold 𝛿 = 16 Time (s) Comm. (MB) 0.14 5.65 1.92 2.21 1.00 4.07 0.85 35.35 4.57 8.98 1.22 8.57 64.27 1053.25 33.18 182.91 4.83 105.06 1.68 84.14 37.46 34.25 4.92 32.20 13.87 560.04 109.56 142.01 8.46 95.39 1278.99 16879.90 579.98 2922.36 79.56 1625.46 6.82 335.67 164 136.48 19.55 121.66 58.44 2241.18 394.26 567.23 36.20 372.31 — — 2591.22 11687.10 379.89 6494.57

Threshold 𝛿 = 64 Time (s) Comm. (MB) 0.15 7.34 1.92 2.21 0.94 4.07 1.08 46.85 4.61 8.98 1.16 8.57 145.74 1401.62 32.93 182.91 4.81 105.06 2.25 111.23 38.73 34.25 5.06 32.20 18.89 744.36 87.58 142.01 8.38 95.39 2653.76 22465.60 582.74 2922.36 79.00 1625.46 9.59 444.02 199.41 136.48 19.43 121.66 80.09 2979.16 399.87 567.23 35.41 372.31 — — 2573.38 11687.10 385.62 6494.57

depending on 𝛿, as their running time grows with (log 𝛿)𝑑/2 . Although this step is executed in plaintext, when combined with the other components, the overall complexity becomes 𝑛 · 2𝑑 · (log 𝛿)𝑑/2 , which constitutes a significant bottleneck as both 𝛿 and 𝑑 increase. Moreover, our construction further reduces communication by up to 20×, since unlike our OT-based fuzzy matching with reduced input domain, the protocol of [46] incur the communication overhead dependent on the statistical security parameter. Compared to [38], our protocol supports a larger input domain (e.g., 64-bit values in our implementation) while achieving lower running time and communication overhead. Specifically, when 𝑚 = 𝑛 = 218 and 𝑑 = 8, our protocol is 7× faster and incurs 1.8× less communication cost than [38]. When extended to larger input domains to support large 𝛿, the overhead of [38] would increase substantially, further highlighting the advantage of our protocols. Results for 𝐿𝑝 Distances. Tables 4 and 5 in Appendix D present the results for 𝐿1 and 𝐿2 distances. We observe that our protocols across the 𝐿∞ , 𝐿1 , and 𝐿2 distance metrics exhibit comparable overall overheads. This is because the constructions execute identical operations, differing exclusively in the O (𝑚) invocations of fuzzy matching (instantiated for either 𝐿∞ or 𝐿𝑝 ). Due to our input domain reduction optimization, the concrete cost of these fuzzy matching operations does not dominate the total execution time. Compared to [46], our protocol achieves up to a 5× computational speedup and a 34× reduction in communication bandwidth. Furthermore, we observe a distinct threshold-dependent performance inversion in [46]: for smaller values of 𝛿, their 𝐿∞ protocol incurs higher overhead than their 𝐿𝑝 counterpart, whereas for larger

Threshold 𝛿 = 256 Time (s) Comm. (MB) 0.21 9.07 1.89 2.21 0.99 4.07 1.34 58.53 4.48 8.98 1.22 8.57 348.73 1755.75 33.07 182.91 4.84 105.06 2.83 138.72 37.37 34.25 4.90 32.20 24.68 931.54 85.56 142.01 8.29 95.39 5830.80 28027.10 574.98 2922.36 78.74 1625.46 11.93 554.06 * * 20.01 121.66 108.71 3728.65 418.17 567.23 36.03 372.31 — — 2606.11 11687.10 388.46 6494.57

Threshold 𝛿 = 1024 Time (s) Comm. (MB) 0.23 10.76 * * 0.96 4.07 1.70 70.11 * * 1.14 8.57 698.87 2106.82 * * 4.78 105.06 3.43 165.97 * * 4.96 32.20 29.34 1117.24 * * 8.35 95.39 11697.40 33637.40 * * 79.04 1625.46 14.80 663.20 * * 19.57 121.66 130.20 4472.26 * * 35.89 372.31 — — * * 384.87 6494.57

𝛿, their 𝐿𝑝 protocol becomes more expensive. This disparity stems from their asymptotic complexities. As outlined in Table 1, the overhead of their 𝐿∞ protocol scales with a multiplicative factor of 2𝑑 𝑑 log 𝛿 (dominating for small 𝛿), while their 𝐿𝑝 construction is bottlenecked by the terms 𝑑𝛿 (dominating for large 𝛿) and 2𝑑 𝑑. Compared to [38], when 𝑚 = 𝑛 = 218 , 𝑑 = 4, and 𝛿 = 256, our protocol achieves up to a 25× speedup and a 17× reduction in communication cost for 𝐿1 distance. Since the protocol in [38] supports only the setting 𝑑 = 2 and 𝛿 ∈ {10, 30} for the 𝐿2 distance, we do not include it in the Table 5. We evaluate our protocol under the same settings (𝑑 = 2 and 𝛿 = {8, 32}), and observe that it reduces the communication and computational cost by up to 4× and 10×, respectively. In some special cases with small parameters, our protocol is less efficient, as the overhead of the underlying silent OT [4] cannot be effectively amortized. Furthermore, the performance of our protocols remains nearly unchanged as 𝛿 increases from 16 to 1024, because in practice we round parameters that depend on log 𝛿 to multiples of 8 to facilitate efficient implementation.

8.2

Performance for High-dimensional Sets

We evaluate our protocols for high-dimensional sets under three distance metrics and compare them with [46], which adopts the same set assumptions as ours and is the state-of-the-art fuzzy PSI for high-dimensional settings. Results of 𝐿∞ distance. As shown in Table 3, the overhead of our protocol for 𝐿∞ scales logarithmically with 𝛿, outperforming the protocol in [46] across all parameter settings, whose complexity

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Table 3: Comparisons of fuzzy PSI over high-dimensional sets for 𝐿∞ distance. "*" indicates unsupported or no implementation for the specific parameter setting. The best result is marked in blue. Set size 𝑚 =𝑛

Dim. 𝑑 16

212

32 64 16

216

32 64 16

218

32 64

Protocol van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours

Threshold 𝛿 = 16 Time (s) Comm. (MB) 0.48 47.24 0.42 27.26 0.91 94.04 0.73 53.56 1.82 187.68 1.43 106.39 7.68 750.94 6.24 424.14 15.94 1501.29 12.85 846.85 33.03 3002.60 27.91 1692.64 32.08 3005.60 25.36 1695.64 66.62 6009.38 52.51 3388.23 136.65 12021.20 110.20 6775.05

grows linearly with 𝛿. In particular, our protocol exhibits a substantial advantage for large distance threshold 𝛿. When 𝑚 = 𝑛 = 212 , 𝑑 = 64, and 𝛿 = 1024, our protocol requires 36× less running time and 54× less communication than [46]. We note that the protocol in [46] requires a large number of OPPRF invocations under some large parameter settings, and no concrete implementation is available for these cases. We thus mark these entries as “*”. Results of 𝐿𝑝 distances. For the 𝐿1 and 𝐿2 distances, our protocol incurs additional overhead due to the invocation of OT-based fuzzy matching. Nevertheless, it still significantly outperforms [46] for most of the parameter settings. The results are presented in Tables 6 and 7 in Appendix D. Specifically, our protocol achieves up to a 20× reduction in running time and a 38× reduction in communication cost.

9

Threshold 𝛿 = 64 Time (s) Comm. (MB) 1.66 177.97 0.47 35.37 3.42 355.64 0.95 69.86 7.24 711.17 1.97 138.85 28.84 2847.02 8.06 554.11 62.01 5695.39 16.52 1106.96 126.33 11395.90 33.68 2213.14 140.46 11398.90 32.86 2216.14 328.44 22744.10 69.22 4429.27 * * 150.63 8859.02

Threshold 𝛿 = 256 Time (s) Comm. (MB) 6.61 701.40 0.61 43.56 13.35 1403.19 1.12 86.35 27.93 2807.27 2.50 171.84 116.36 11239.50 10.08 686.16 261.13 22430.60 20.75 1371.10 * * 42.52 2741.69 * * 42.69 2744.69 * * 88.19 5487.53 * * 186.29 10975.40

Threshold 𝛿 = 1024 Time (s) Comm. (MB) 25.99 2797.59 0.70 51.69 54.17 5597.20 1.40 102.67 109.52 11199.90 3.00 204.53 * * 12.15 817.09 * * 24.75 1633.09 * * 50.47 3266.10 * * 50.47 3269.10 * * 105.49 6536.69 * * 245.43 13075.30

Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grants (Proposal ID: 24-SIS-SMU-052, 24-SIS-SMU-126). This work is also supported by the Nanyang Technological University Centre in Computational Technologies for Finance (NTU-CCTF), the National Research Foundation, Singapore, and Cyber Security Agency of Singapore under its National Cybersecurity R&D Programme and CyberSG R&D Cyber Research Programme Office. This work is also supported by the National Natural Science Foundation of China under Grant 62502079, the China Postdoctoral Science Foundation under Grant BX20240053, and the Sichuan Natural Science Foundation 2026NSFSC1463. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of NTU-CCTF, National Research Foundation, Singapore, Cyber Security Agency of Singapore as well as CyberSG R&D Programme Office, Singapore.

Conclusion

We present scalable fuzzy PSI protocols for general 𝐿𝑝 ∈ [1,∞] distance, supporting both low- and high-dimensional sets. Our core techniques include two asymptotically efficient fuzzy matching protocols: one based on a customized role-reversed OPRF and another on OT. For low-dimensional sets, we introduce a dual-layer hashing framework that significantly reduces the number of fuzzy matching invocations, while for high-dimensional sets, we enhance existing fuzzy PSI constructions to achieve linear complexity in set size and dimension, with logarithmic complexity in the distance threshold. Overall, our work advances prior fuzzy PSI protocols both concretely and asymptotically.

Acknowledgments We would like to express our deepest gratitude to the reviewers for their invaluable help and constructive comments. This work is supported by the Lee Kong Chian Chair Professorship, Singapore Management University. Guomin Yang is supported by the Lee Kong Chian Fellowship awarded by Singapore Management University. This work is supported by the Singapore

Ethical Considerations This work provides effective solutions for fuzzy private set intersection tasks. The experiments in this paper are all based on synthetic datasets and do not contain any personal or illegal information. We firmly believe that our research was done ethically.

Open Science We follow the principles of the Open Science Policy. Our artifacts include the source code of our protocols, benchmarking scripts, and detailed operation documentation. We have consolidated these research artifacts into an open-source repository, and our artifacts are available at https://github.com/Th0masAndy/Scalable-FPSI and https://doi.org/10.5281/zenodo.20607518.

Generative AI Usage This paper used the LLM (including ChatGPT and Gemini) solely to assist with grammar checking and language polishing.

CCS ’26, November 15–19, 2026, The Hague, Netherlands

References [1] Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, and Peter Rindal. 2024. Improved alternating-moduli PRFs and post-quantum signatures. In Annual International Cryptology Conference. 274–308. [2] Alexander Bienstock, Sarvar Patel, Joon Young Seo, and Kevin Yeo. 2023. Nearoptimal oblivious key-value stores for efficient PSI, PSU and volume-hiding multi-maps. In USENIX Security Symposium. 301–318. [3] Erik-Oliver Blass and Guevara Noubir. 2025. Assumption-free fuzzy PSI via predicate encryption. Cryptology ePrint Archive, Paper 2025/217. https://eprint. iacr.org/2025/217 [4] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. 2019. Efficient two-round OT extension and silent noninteractive secure computation. In ACM SIGSAC Conference on Computer and Communications Security. 291–308. [5] Elette Boyle, Niv Gilboa, and Yuval Ishai. 2015. Function secret sharing. In Annual international conference on the theory and applications of cryptographic techniques. Springer, 337–367. [6] Elette Boyle, Niv Gilboa, and Yuval Ishai. 2016. Function secret sharing: Improvements and extensions. In ACM SIGSAC conference on computer and communications security. 1292–1303. [7] Dung Bui, Gayathri Garimella, Peihan Miao, and Phuoc Van Long Pham. 2025. New framework for structure-aware PSI from distributed function secret sharing. In International Conference on the Theory and Application of Cryptology and Information Security. 294–326. [8] Anrin Chakraborti, Giulia Fanti, and Michael K Reiter. 2023. Distance-aware private set intersection. In USENIX Security Symposium. 319–336. [9] Melissa Chase, Esha Ghosh, and Oxana Poburinnaya. 2020. Secret-shared shuffle. In International conference on the theory and application of cryptology and information security. 342–372. [10] Lukasz Chmielewski and Jaap-Henk Hoepman. 2008. Fuzzy private matching. In International Conference on Availability, Reliability and Security. 327–334. [11] Chengrui Dang, Xv Zhou, and Bei Liang. 2025. Efficient fuzzy PSI based on prefix representation. In ACM SIGSAC Conference on Computer and Communications Security. [12] Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY-A framework for efficient mixed-protocol secure two-party computation. In Network and Distributed System Security Symposium. [13] Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha. 2021. MPC-friendly symmetric cryptography from alternating moduli: Candidates, protocols, and applications. In Annual International Cryptology Conference. Springer, 517–547. [14] Changyu Dong, Liqun Chen, and Zikai Wen. 2013. When private set intersection meets big data: an efficient and scalable protocol. In ACM SIGSAC conference on Computer and communications security. 789–800. [15] Michael J Freedman, Kobbi Nissim, and Benny Pinkas. 2004. Efficient private matching and set intersection. In International conference on the theory and applications of cryptographic techniques. 1–19. [16] Ying Gao, Lin Qi, Xiang Liu, Yuanchao Luo, and Longxin Wang. 2024. Efficient fuzzy private set intersection from fuzzy mapping. In International Conference on the Theory and Application of Cryptology and Information Security. 36–68. [17] Gayathri Garimella, Benjamin Goff, and Peihan Miao. 2024. Computation efficient structure-aware psi from incremental function secret sharing. In Annual International Cryptology Conference. 309–345. [18] Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. 2021. Oblivious key-value stores and amplification for private set intersection. In International Cryptology Conference. 395–425. [19] Gayathri Garimella, Mike Rosulek, and Jaspal Singh. 2022. Structure-aware private set intersection, with applications to fuzzy matching. In Annual International Cryptology Conference. 323–352. [20] Google. 2019. Better password protections in Chrome - How it works. https://security.googleblog.com/2019/12/better-password-protectionsin-chrome.html Last accessed 11 November 2025. [21] Xiaojie Guo, Kang Yang, Xiao Wang, Wenhao Zhang, Xiang Xie, Jiang Zhang, and Zheli Liu. 2023. Half-tree: Halving the cost of tree expansion in COT and DPF. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. 330–362. [22] Feng Han, Xiao Lan, Weiran Liu, Lei Zhang, Hao Ren, Lin Qu, and Yuan Hong. 2025. Concretely efficient correlated oblivious permutation. Cryptology ePrint Archive, Paper 2025/449. https://eprint.iacr.org/2025/449 [23] Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. 2022. Iron: Private inference on transformers. Advances in neural information processing systems 35 (2022), 15718–15731. [24] Meng Hao, Weiran Liu, Liqiang Peng, Hongwei Li, Cong Zhang, Hanxiao Chen, and Tianwei Zhang. 2024. Unbalanced circuit-PSI from oblivious key-value retrieval. In USENIX Security Symposium. 6435–6451. [25] Ellis Horowitz and Sartaj Sahni. 1974. Computing partitions with applications to the knapsack problem. J. ACM 21, 2 (1974), 277–292.

Meng Hao et al.

[26] Zhicong Huang, Wen-jie Lu, Cheng Hong, and Jiansheng Ding. 2022. Cheetah: Lean and fast secure two-party deep neural network inference. In USENIX Security Symposium. 809–826. [27] Piotr Indyk and David Woodruff. 2006. Polylogarithmic private approximations and efficient matching. In Theory of Cryptography Conference. 245–264. [28] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. 2019. Mobile private contact discovery at scale. In USENIX Security Symposium. 1447–1464. [29] Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. 2016. Efficient batched oblivious PRF with applications to private set intersection. In ACM SIGSAC Conference on Computer and Communications Security. 818–829. [30] Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu. 2017. Practical multi-party private set intersection from symmetric-key techniques. In ACM SIGSAC Conference on Computer and Communications Security. 1257–1272. [31] Rasmus Pagh and Flemming Friche Rodler. 2004. Cuckoo hashing. Journal of Algorithms (2004), 122–144. [32] Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal, and Harshal Shah. 2025. Efficient permutation correlations and batched random access for two-party computation. In IACR International Conference on Public-Key Cryptography. 76– 109. [33] Lance Roy Peter Rindal. [n. d.]. libOTe: an efficient, portable, and easy to use Oblivious Transfer Library. https://github.com/osu-crypto/libOTe. [34] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. 2020. PSI from PaXoS: Fast, malicious private set intersection. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. 739–767. [35] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. 2015. Phasing: Private set intersection using permutation-based hashing. In USENIX Security Symposium. 515–530. [36] Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai. 2019. Efficient circuit-based PSI with linear communication. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 122–153. [37] Benny Pinkas, Thomas Schneider, and Michael Zohner. 2018. Scalable private set intersection based on OT extension. ACM Transactions on Privacy and Security (2018), 1–35. [38] Lucas Piske, Jaspal Singh, Ni Trieu, Vladimir Kolesnikov, and Vassilis Zikas. 2025. Distance-aware OT with application to fuzzy PSI. In ACM SIGSAC Conference on Computer and Communications Security. [39] Srinivasan Raghuraman and Peter Rindal. 2022. Blazing fast PSI from improved OKVS and subfield VOLE. In ACM SIGSAC Conference on Computer and Communications Security. 2505–2517. [40] Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, and Aseem Rastogi. 2021. Sirnn: A math library for secure rnn inference. In IEEE Symposium on Security and Privacy. 1003–1020. [41] Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. 2020. Cryptflow2: Practical 2-party secure inference. In ACM SIGSAC Conference on Computer and Communications Security. 325–342. [42] David Richardson, Mike Rosulek, and Jiayu Xu. 2024. Fuzzy PSI via oblivious protocol routing. Cryptology ePrint Archive, Paper 2024/1642. https://eprint. iacr.org/2024/1642 [43] Peter Rindal and Phillipp Schoppmann. 2021. VOLE-PSI: fast OPRF and circuit-PSI from vector-OLE. In Annual international conference on the theory and applications of cryptographic techniques. 901–930. [44] Erkam Uzun, Simon P Chung, Vladimir Kolesnikov, Alexandra Boldyreva, and Wenke Lee. 2021. Fuzzy labeled private set intersection with applications to private real-time biometric search. In USENIX Security Symposium. 911–928. [45] Aron van Baarsen and Sihang Pu. 2024. Fuzzy private set intersection with large hyperballs. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. 340–369. [46] Aron van Baarsen and Sihang Pu. 2025. Fuzzy private set intersection from VOLE. In International Conference on the Theory and Application of Cryptology and Information Security. [47] Mingli Wu and Tsz Hon Yuen. 2023. Efficient unbalanced private set intersection cardinality and user-friendly privacy-preserving contact tracing. In USENIX Security Symposium. 283–300. [48] Andrew C Yao. 1982. Protocols for secure computations. In annual symposium on foundations of computer science. 160–164. [49] Qingsong Ye, Ron Steinfeld, Josef Pieprzyk, and Huaxiong Wang. 2009. Efficient fuzzy matching and intersection on private datasets. In International Conference on Information Security and Cryptology. 211–228. [50] Cong Zhang, Yu Chen, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Anyu Wang, and Xiaoyun Wang. 2025. Fast fuzzy PSI from symmetric-key techniques. Cryptology ePrint Archive, Paper 2025/885. https://eprint.iacr.org/2025/885

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

A

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Assumption of Unique Ball/Center

𝐿𝑝

Protocol Π FMatch-ot

Our work uses the unique ball/center as the assumption, which is essentially the same as that used in [38, 46] with different representations. For example, [46] assumes that for any 𝐿𝑝 ∈ [1,∞] distance, the sender’s points are 2𝛿 (𝑑 1/𝑝 )-apart and the receiver’s points are 2𝛿 (𝑑 1/𝑝 + 1)-apart. As illustrated in [45, 46], this implies the unique ball/center. We recall their conclusion as follows. Lemma A.1 (Uniqe Center [45, 46]). Suppose there are multiple 𝐿𝑝 balls (𝑝 ∈ [1, ∞]) with radius 𝛿 lying in a 𝑑-dimensional space which is tiled by cells with side length 2𝛿. If these balls’ centers are at least 2𝛿𝑑 1/𝑝 apart from each other, then for each cell, there is at most one center lying in this cell. Specifically, if 𝑝 = ∞, then this holds for disjoint balls, since 2𝛿𝑑 1/𝑝 degrades to 2𝛿 in this case. Lemma A.2 (Uniqe Ball [45, 46]). Suppose there are multiple 𝐿𝑝 balls (𝑝 ∈ [1, ∞]) with radius 𝛿 lying in a 𝑑-dimensional space which is tiled by cells with side length 2𝛿. If these balls’ centers are at least 2𝛿 (𝑑 1/𝑝 + 1) apart from each other, then there exists at most one ball intersecting with the same cell. Specifically, if 𝑝 = ∞, then this holds for 𝐿∞ balls with 4𝛿-apart centers.

B Details of OT-based Fuzzy Matching B.1 Additional Functionalities Our OT-based fuzzy matching protocols rely on several customized OT-based primitives for securely computing the most significant bit, multiplication, and absolute value. Below, we summarize the corresponding ideal functionalities and their communication overhead of state-of-the-art protocols. (1) Most significant bit (MSB). The functionality FMSB takes as input [𝑥] ℓ and outputs [𝑦] 1 , where 𝑦 = MSB(𝑥). Existing works [26, 41] provide efficient protocols with communication cost below 11ℓ bits and log ℓ communication rounds. (2) AND. The functionality FAND takes as input {[𝑥𝑖 ] 1 }𝑖 ∈ [𝑑 ] and outputs [𝑦] 1 , where 𝑦 = 𝑥 1 ∧ · · · ∧ 𝑥𝑑 . We generate random AND triples using silent OT [4], and then perform Beaverstyle multiplications with 4(𝑑 − 1) bits of communication and log 𝑑 rounds. (3) Absolute values (ABS). The functionality FABS takes as input [𝑥] ℓ and outputs [𝑦] ℓ , where 𝑦 = |𝑥 |. This functionality can be securely realized using MUX and MSB operations [23, 26, 40, 41]. The protocol requires 13ℓ bits of communication and log ℓ rounds. (4) Multiplication (Mult). The functionality FMult takes as input ( [𝑥] ℓ , [𝑦] ℓ ) and outputs [𝑧] ℓ , where 𝑧 = 𝑥 · 𝑦. We employ correlated-OT-based protocols from [12, 40], which incur communication of ℓ 2 /2 bits with 2 rounds.

B.2

OT-based Fuzzy Matching for 𝐿𝑝 Distance

We can extend OT-based fuzzy matching to arbitrary 𝐿𝑝 distance. In Figure 15, we propose efficient protocols for widely used 𝐿1 and 𝐿2 distances by using MSB, ABS, and multiplication functionalities as shown in Appendix B.1. Our protocol incurs an overhead of

Parameter: Sender S and receiver R. Threshold 𝛿. Input: S inputs 𝒒 = (𝑞 1 , . . . , 𝑞𝑑 ) ∈ Z𝑑2ℓ and R inputs 𝒘 = (𝑤1 , . . . , 𝑤𝑑 ) ∈ Z𝑑2ℓ . Protocol: (1) For 𝑘 ∈ [𝑑 ], S and R compute [𝑡𝑘 ] ℓ := 𝑞𝑘 − 𝑤𝑘 . (2) For 𝑘 ∈ [𝑑 ], S and R executes as follows and learn [ 𝑓𝑘 ] ℓ . • 𝑝 = 1: Invoke functionality FABS with input [𝑡𝑘 ] ℓ . • 𝑝 = 2: Invoke functionality FMult with input ( [𝑡𝑘 ] ℓ , [𝑡𝑘 ] ℓ ). Í (3) S and R locally compute [ 𝑓 ] ℓ := 𝛿 𝑝 − 𝑘 ∈ [𝑑 ] [ 𝑓𝑘 ] ℓ . S and R invoke functionality FMSB with inputs [ 𝑓 ] ℓ and learn [𝑧 ] 1 . (4) S sends 1 ⊕ [𝑧 ] 1S to R, who outputs 𝑧 := 1 ⊕ [𝑧 ] 1S ⊕ [𝑧 ] 1R .

Figure 15: Protocol of fuzzy matching for 𝐿𝑝 distance from OT 𝑂 (𝑝𝑑ℓ) in both communication4 and computation. The security of the protocol is shown as follows, and we defer the detailed correctness and security analysis to Appendix E.3. 𝑝 Theorem B.1. The protocol ΠFMatch-OT in Figure 15 realizes the functionality FFMatch for 𝐿𝑝 distance in Figure 1 against semi-honest adversaries in the (FABS, FMult, FMSB )-hybrid model.

𝐿

C

Details of Fuzzy PSI for High-dimensional Sets

In this section, we introduce the details of our fuzzy PSI for highdimensional sets. Fuzzy PSI for 𝐿∞ distance. We compile our OPRF-based fuzzy matching protocol to construct fuzzy PSI for 𝐿∞ distance. Our protocol follows a similar high-level framework to that of [46]; however, a key distinction is that our construction supports prefixtrie techniques in combination with our asymptotically efficient fuzzy matching. As discussed in [46], prefix-trie techniques are not incorporated in their protocol because doing so incurs a computation cost of (log 𝛿)𝑑/2 , which becomes prohibitively large in high-dimensional settings. Recall that in our OPRF-based fuzzy matching protocol, for each dimension 𝑘, the OPPRF programs (a prefix representation of) the interval [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿] to a single random value 𝑟𝑘 . To extend this construction to multi-point fuzzy PSI, the natural approach is to perform OPPRF evaluations over all sender and receiver points. However, there are two important requirements. First, the intervals [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿] and [𝑞𝑘′ − 𝛿, 𝑞𝑘′ + 𝛿] corresponding to two distinct sender points cannot overlap, since OPPRF cannot program the same input to two different values 𝑟𝑘 and 𝑟𝑘′ . Second, any two receiver queries 𝑤𝑘 and 𝑤𝑘′ must not fall into the same programmed interval [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿]; otherwise, the receiver would obtain the same value 𝑟𝑘 for both queries, which leaks additional information about partial matches on individual dimensions. Fortunately, the globally disjoint assumption satisfies these requirements. Under 4We note that the OT-based multiplication protocol incurs 𝑂 (ℓ 2 ) communication.

However, an alternative solution is to employ efficient RLWE-based additively homomorphic encryption, which incurs 𝑂 (ℓ ) communication. Therefore, we maintain the 𝑂 (𝑝𝑑ℓ ) communication overhead in our asymptotic analysis.

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Meng Hao et al.

Table 4: Comparisons of fuzzy PSI over low-dimensional sets for 𝐿1 distance. "*" indicates unsupported or no implementation for the specific parameter setting. The best result is marked in blue. Set size 𝑚 =𝑛

Dim. 𝑑 2

212

4

8

2

216

4

8

2

218

4

8

Protocol van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours van Baarsen & Pu [46] Piske et al. [38] Ours

Threshold 𝛿 = 16 Time (s) Comm. (MB) 0.11 7.33 1.95 5.9 0.66 3.17 0.27 18.01 4.63 16.35 0.87 6.84 4.78 198.62 34.56 197.63 4.73 101.69 1.45 111.14 39.46 93.03 3.81 27.32 4.76 282.25 91.97 259.52 6.72 85.73 92.57 3177.7 592.08 3157.32 78.13 1606.23 5.83 443.64 171.61 371.44 15.81 104.72 19.89 1128.75 411.09 1037.06 28.64 338.53 439.35 12721.40 2639.26 12626.70 366.60 6427.12

Threshold 𝛿 = 64 Time (s) Comm. (MB) 0.27 23.9 2.23 13.88 0.64 3.17 0.63 51.04 5.36 32.28 0.89 6.84 5.7 264.58 35.54 229.47 4.64 101.69 4.06 376.74 46.25 220.31 3.94 27.32 10.61 811.74 109.06 514.02 6.9 85.73 109.22 4235.31 623.35 3666.25 77.66 1606.23 17.82 1507.24 196.34 880.37 16.30 104.72 46.41 3248.83 465.84 2054.81 28.71 338.53 521.57 16955.50 2781.08 14663.3 395.73 6427.12

Threshold 𝛿 = 256 Time (s) Comm. (MB) 0.91 89.48 3.59 43.73 0.79 3.17 1.94 182.15 8.26 91.96 0.89 6.84 9.17 526.82 40.62 348.8 4.38 101.69 14.69 1428.29 79.94 697.43 3.96 27.32 33.35 2913.84 159.56 1468.18 6.69 85.73 205.05 8439.44 734.61 5574.42 77.7 1606.23 63.13 5717.38 323.33 2788.54 16.40 104.72 146.63 11665.30 748.99 5870.97 29.30 338.53 814.18 33730.60 3361.54 22294.10 373.99 6427.12

Threshold 𝛿 = 1024 Time (s) Comm. (MB) 3.35 351.33 * * 0.75 3.17 7.02 705.97 * * 0.86 6.84 20.15 1575.00 * * 3.60 134.77 58.81 5626.30 * * 4.20 27.32 168.91 11312.50 * * 6.61 85.73 485.63 25184.90 * * 68.39 2136.62 264.72 22468.90 * * 15.98 104.72 * * * * 28.94 338.53 * * * * 326.58 8551.02

Table 5: Comparisons of fuzzy PSI over low-dimensional sets for 𝐿2 distance. "*" indicates unsupported or no implementation for the specific parameter setting. The best result is marked in blue. Set size 𝑚 =𝑛

Dim. 𝑑 2

212

4 8 2

216

4 8 2

218

4 8

Protocol van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours

Threshold 𝛿 = 16 Time (s) Comm. (MB) 0.14 7.83 0.59 2.88 0.33 18.76 0.60 6.54 5.32 199.87 4.04 101.39 1.66 119.14 3.12 27.19 5.49 294.25 5.21 85.85 100.28 3197.70 73.01 1606.89 6.99 475.64 13.35 105.38 22.45 1176.75 22.93 340.32 482.04 12801.40 365.36 6431.17

this assumption, after invoking our role-reversed OPPRF, the sender obtains an identifier id𝒒 𝑗 for each 𝒒 𝑗 ∈ 𝑄, and the receiver obtains an identifier id𝒘𝑖 for each 𝒘𝑖 ∈ 𝑊 , such that id𝒒 𝑗 = id𝒘𝑖 if and only if dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. Finally, both parties engage in a labeled PSI protocol (see Section 3.6), which enables the receiver to obtain 𝒒 𝑗 corresponding to the matched identifiers.

Threshold 𝛿 = 64 Time (s) Comm. (MB) 0.29 24.65 0.57 3.32 0.72 52.17 0.73 8.13 6.41 266.46 3.24 134.97 4.42 388.74 3.65 34.17 11.60 829.74 6.83 111.34 123.78 4265.31 58.71 2145.39 19.69 1555.24 14.42 133.38 47.77 3320.83 29.76 442.52 592.76 17075.50 350.83 8587.77

Threshold 𝛿 = 256 Time (s) Comm. (MB) 0.94 90.48 0.58 3.32 2.09 183.65 0.74 8.13 10.08 529.32 3.23 134.97 15.92 1444.29 3.77 34.17 36.25 2937.84 6.93 111.34 187.23 8479.44 65.18 2145.39 68.85 5781.38 14.95 133.38 187.45 11761.30 29.84 442.52 898.91 33890.60 306.63 8587.77

Threshold 𝛿 = 1024 Time (s) Comm. (MB) 3.93 352.58 0.57 3.85 7.82 707.84 0.74 9.88 22.89 1578.13 4.13 169.34 68.34 5646.3 3.86 42.44 162.54 11342.5 7.61 139.33 423.36 25234.90 73.79 2696.60 298.37 22548.90 15.51 166.64 * * 32.26 554.86 * * 383.05 10795.40

Fuzzy PSI for 𝐿𝑝 distance. We further extend the above protocol to 𝐿𝑝 distance. The above protocol for 𝐿∞ distance before the last weak label PSI can be viewed as a fuzzy mapping operation. This operation assign an unique identifier id𝒒 𝑗 for each 𝒒 𝑗 , similarly id𝒘𝑖 for each 𝒘𝑖 , satisfying id𝒒 𝑗 = id𝒘𝑖 if dist∞ (𝒘𝑖 , 𝒒 𝑗 ) ≤ 𝛿. To precisely determine the 𝐿𝑝 distance, both parties need to execute fuzzy matching on the pairs sharing the same identifier. Since our

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

CCS ’26, November 15–19, 2026, The Hague, Netherlands

Table 6: Comparisons of fuzzy PSI over high-dimensional sets for 𝐿1 distance. "*" indicates unsupported or no implementation for the specific parameter setting. The best result is marked in blue. Set size 𝑚 =𝑛

Dim. 𝑑 16

212

32 64 16

216

32 64 16

218

32 64

Protocol van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours

Threshold 𝛿 = 16 Time (s) Comm. (MB) 0.46 49.49 2.93 39.32 0.90 98.29 5.29 74.79 1.88 195.93 9.49 145.93 7.99 786.94 40.97 592.16 16.13 1569.29 81.10 1164.54 33.04 3134.60 158.10 2309.64 35.17 3149.60 173.76 2364.69 70.20 6281.38 381.05 4659.33 142.61 12549.20 974.50 9250.23

Threshold 𝛿 = 64 Time (s) Comm. (MB) 1.68 181.35 3.18 47.43 3.38 362.02 5.94 91.09 6.86 723.55 10.15 178.39 28.99 2901.02 42.51 722.14 60.04 5797.39 82.17 1424.65 126.01 11593.90 179.22 2830.14 129.34 11614.90 182.71 2885.19 293.72 23152.10 399.78 5700.37 * * 1023.99 11334.20

Threshold 𝛿 = 256 Time (s) Comm. (MB) 7.29 705.9 2.98 55.62 13.68 1411.69 5.66 107.58 30.28 2823.77 10.31 211.37 115.97 11311.50 45.33 854.18 252.21 22566.60 86.62 1688.79 * * 179.47 3358.68 * * 195.19 3413.73 * * 445.68 6758.63 * * 1069.14 13450.60

Threshold 𝛿 = 1024 Time (s) Comm. (MB) 26.95 2803.22 3.37 63.75 54.73 5607.82 5.96 123.90 115.75 11220.50 11.36 244.06 * * 47.45 985.11 * * 92.64 1950.79 * * 189.75 3883.10 * * 225.93 3938.15 * * 438.60 7807.79 * * 1118.85 15550.50

Table 7: Comparisons of fuzzy PSI over high-dimensional sets for 𝐿2 distance. "*" indicates unsupported or no implementation for the specific parameter setting. The best result is marked in blue. Set size 𝑚 =𝑛

Dim. 𝑑 16

212

32 64 16

216

32 64 16

218 32

Protocol van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours van Baarsen & Pu [46] Ours

Threshold 𝛿 = 16 Time (s) Comm. (MB) 0.48 51.74 1.51 50.35 0.93 102.54 2.43 97.25 1.88 204.18 4.23 191.26 8.14 822.94 18.86 777.21 16.55 1637.29 33.28 1535.14 33.01 3266.60 72.69 3051.35 35.68 3293.60 83.30 3111.16 77.92 6553.38 150.70 6152.83

OPRF-based fuzzy matching can not support 𝐿𝑝 distance, we use our OT-based fuzzy matching and follow the Cuckoo-hashing-based strategy of our fuzzy PSI for low-dimensional sets. We further optimize the input domain used in the OT-based fuzzy matching phase. Our key observation is that for any points 𝒒 𝑗 and 𝒘𝑖 , having the same identifier id𝒒 𝑗 = id𝒘𝑖 implies dist∞ (𝒘𝑖 , 𝒒 𝑗 ) ≤ 𝛿. Consequently, for every dimension 𝑘 ∈ [𝑑], it holds that |𝑤𝑖,𝑘 − 𝑞 𝑗,𝑘 | ≤ 𝛿. As shown in our OT-based fuzzy matching protocol in Figure 15, the first step computes 𝑡𝑘 = 𝑤𝑖,𝑘 − 𝑞 𝑗,𝑘 , which lies in the range [−𝛿, 𝛿]. Therefore, we can represent its secret shares using a smaller bit length. This optimization significantly reduces the overhead of subsequent operations whose complexity depends on the bit length of the secret sharing. We follow a strategy similar to our fuzzy PSI protocol for low-dimensional sets in Figure 11 to address false positives caused by the reduced input domain.

Threshold 𝛿 = 64 Time (s) Comm. (MB) 1.71 184.72 1.68 58.47 3.44 368.39 2.65 113.55 6.96 735.92 4.72 223.72 30.03 2955.02 20.44 907.18 60.64 5899.39 38.38 1795.25 126.18 11791.90 73.45 3571.85 130.30 11830.90 92.05 3631.66 341.46 23560.10 168.78 7193.88

D

Threshold 𝛿 = 256 Time (s) Comm. (MB) 6.76 710.40 1.76 66.66 13.82 1420.19 2.86 130.04 27.48 2840.27 5.04 256.70 117.34 11383.50 22.12 1039.23 263.34 22702.60 41.36 2059.38 * * 82.49 4100.39 * * 102.04 4160.21 * * 183.38 8252.13

Threshold 𝛿 = 1024 Time (s) Comm. (MB) 28.63 2808.84 1.97 74.79 57.93 5618.45 3.23 146.36 116.44 11241.20 5.83 289.39 * * 25.85 1170.16 * * 47.27 2321.38 * * 91.7 4624.81 * * 106.12 4684.62 * * 214.89 9301.29

Additional Experimental Results

We provide additional experimental results for 𝐿𝑝 distance. Specifically, Tables 4 and 5 report the performance comparisons of fuzzy PSI over low-dimensional sets for 𝐿1 and 𝐿2 distance, respectively. Tables 6 and 7 report the performance comparisons of fuzzy PSI over high-dimensional sets for 𝐿1 and 𝐿2 distance, respectively.

E Security Proofs E.1 Proof of Theorem 5.1 Proof. We first establish the correctness of the protocol by analyzing the prefix matching and parameter bounds, and then construct simulators to demonstrate that the simulated execution is indistinguishable from the real-world protocol execution. Correctness. We first consider the matching case, where it holds that dist∞ (𝒒, 𝒘) ≤ 𝛿. This implies that 𝑤𝑘 ∈ [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿] for all

CCS ’26, November 15–19, 2026, The Hague, Netherlands

dimensions 𝑘 ∈ [𝑑]. By Theorem 3.1, for each 𝑘 ∈ [𝑑], there exists a unique index 𝑡𝑘∗ ∈ [𝑢 ′ ] such that 𝑤˜ 𝑘,𝑡 ∗ ∈ {𝑞˜𝑘,𝑡 }𝑡 ∈ [𝑢 ] . By the correct𝑘 ness of the first FOPPRF , the receiver successfully learns 𝑟ˆ𝑘,𝑡 ∗ = 𝑟𝑘 , 𝑘 while the remaining evaluations {𝑟ˆ𝑘,𝑡 }𝑡 ≠𝑡 ∗ are independent and 𝑘 uniformly random. To ensure the second FOPPRF is correctly programmed, all elements in {𝑟ˆ𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] must be distinct. As analyzed in the mismatch case below, setting ℓ1 appropriately guarantees this distinctness with overwhelming probability. Consequently, by the correctness of the second FOPPRF , the sender learns 𝑠𝑘 = 𝑠ˆ𝑘 for ˆ and by the correctness of FPEQT , the all 𝑘 ∈ [𝑑]. This yields 𝑠 = 𝑠, receiver obtains the correct output 1. We now consider the mismatch case where dist∞ (𝒒, 𝒘) > 𝛿. This implies there exists at least one dimension 𝑘 ∗ such that 𝑤𝑘 ∗ ∉ [𝑞𝑘 ∗ − 𝛿, 𝑞𝑘 ∗ + 𝛿]. By Theorem 3.1, the corresponding prefix sets are disjoint: {𝑞˜𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ] ∩ {𝑤˜ 𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] = ∅. Therefore, by the correctness of FOPPRF , all evaluations {𝑟ˆ𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] obtained by the receiver are uniformly random and independent of uniformly random 𝑟𝑘 ∗ . To ensure correctness, we must ensure two conditions: (1) no value in {𝑟ˆ𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] accidentally equals 𝑟𝑘 ∗ to avoid false positives, and (2) all values in {𝑟ˆ𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] are distinct, preventing collisions when programming the second FOPPRF . In a single dimension, both requirements hold except with probability at most (𝑢 ′ + 1) 2 /2ℓ1 . By setting the field size to ℓ1 := 𝜆 + 2 log(𝑢 ′ + 1) + log 𝑑, a union bound guarantees these conditions hold simultaneously across all 𝑑 dimensions except with negligible probability in the security parameter 𝜆. Under this parameterization, the evaluation query 𝑟𝑘 ∗ is unprogrammed in the second FOPPRF , resulting in 𝑠𝑘 ∗ being uniformly random. Because the dimensions are evaluated independently, the Í Í aggregate sum 𝑠 = 𝑘 ∈ [𝑑 ] 𝑠𝑘 and 𝑠ˆ = 𝑘 ∈ [𝑑 ] 𝑠ˆ𝑘 are also uniformly random. Setting ℓ2 := 𝜆 ensures the probability of an accidental collision 𝑠 = 𝑠ˆ is bounded by 1/2𝜆 , which is negligible. Thus, FPEQT outputs 0, completing the correctness analysis. Corrupted Sender. We construct a simulator Sim S for a semihonest corrupted sender. Given the sender’s input 𝒒, Sim S runs the adversary A and proceeds as follows: (1) Simulating FOPPRF (Step 2): Sim S receives the programmed points {(𝑘 ∥𝑞˜𝑘,𝑡 , 𝑟𝑘 )}𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ] generated by A. Sim S samples a random function 𝐹 such that 𝐹 (𝑘 ∥𝑞˜𝑘,𝑡 ) = 𝑟𝑘 for 𝑘 ∈ [𝑑], 𝑡 ∈ [𝑢], and sends O 𝐹 to A. (2) Simulating FOPPRF (Step 3): After receiving {𝑘 ∥𝑟𝑘 }𝑘 ∈ [𝑑 ] from A, Sim S samples {𝑠𝑘 }𝑘 ∈ [𝑑 ] ← F2ℓ2 , and sends them to A. (3) Simulating FPEQT (Step 5): Sim S receives 𝑠 from A, and returns nothing. We demonstrate the security of the simulation through a sequence of hybrid games: • Hyb0 : This is the real protocol execution. • Hyb1 : This hybrid behaves identically to Hyb0 , except that instead of passing the honest receiver’s input 𝑠ˆ to FPEQT (Step 5), Sim S receives 𝑠 from A and returns nothing, which perfectly simulates the FPEQT ’s behavior. Thus, the views in Hyb0 and Hyb1 are perfectly identical. • Hyb2 : This hybrid behaves identically to Hyb1 , except that instead of passing the honest receiver’s programmed points to FOPPRF (Step 3), Sim S receives A’s queries {𝑘 ∥𝑟𝑘 }𝑘 ∈ [𝑑 ] and returns uniformly random values 𝑠𝑘 ← F2ℓ2 for all 𝑘 ∈ [𝑑] to A. In Hyb1 , 𝑠𝑘 is either equal to the receiver’s choice

Meng Hao et al.

𝑠ˆ𝑘 (upon a match) or is a random function output. Because the honest receiver samples 𝑠ˆ𝑘 ← F2ℓ2 uniformly at random, every 𝑠𝑘 in Hyb1 is perfectly uniform and independent of A’s view. Thus, the views in Hyb1 and Hyb2 are perfectly identical. • Hyb3 : This hybrid behaves identically to Hyb2 , except that instead of passing honest receiver’s inputs {𝑘 ∥𝑤˜ 𝑘,𝑡 }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] to FOPPRF (Step 2), Sim S receives the programmed points {(𝑘 ∥𝑞˜𝑘,𝑡 , 𝑟𝑘 )}𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ] from A, samples a random function 𝐹 such that 𝐹 (𝑘 ∥𝑞˜𝑘,𝑡 ) = 𝑟𝑘 for 𝑘 ∈ [𝑑], 𝑡 ∈ [𝑢], and sends O 𝐹 to A. Since the real functionality also returns O 𝐹 according to these programmed points, the views in Hyb2 and Hyb3 are perfectly identical. The final hybrid Hyb3 is exactly the simulated execution of Sim S . Therefore, the simulated view is perfectly indistinguishable from the real execution. Corrupted Receiver. We construct a simulator Sim R for a semihonest corrupted receiver. Given the receiver’s input 𝒘 and the ideal output 𝑧, Sim R runs A and proceeds as follows: (1) Simulating FOPPRF (Step 2): After receiving the A’s queries {𝑘 ∥𝑤˜ 𝑘,𝑡 }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] , Sim R samples {𝑟ˆ𝑘,𝑡 }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] ← F2ℓ1 , and returns them to A. (2) Simulating FOPPRF (Step 3): Sim R receives the programmed points {(𝑘 ∥𝑟ˆ𝑘,𝑡 , 𝑠ˆ𝑘 )}𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] from A. Sim R samples a random function 𝐹 ′ such that 𝐹 ′ (𝑘 ∥𝑟ˆ𝑘,𝑡 ) = 𝑠ˆ𝑘 for 𝑘 ∈ [𝑑], 𝑡 ∈ ′ [𝑢 ′ ] and returns O 𝐹 to A. (3) Simulating FPEQT (Step 5): Sim R receives the aggregate sum 𝑠ˆ from A, and returns the ideal output 𝑧 to A. We demonstrate the security of the simulation through a sequence of hybrid games: • Hyb0 : This is the real protocol execution. • Hyb1 : This hybrid behaves identically to Hyb0 , except that instead of passing the honest sender’s input 𝑠 to FPEQT (Step 5), Sim R receives A’s aggregate sum 𝑠ˆ and directly returns the ideal output 𝑧 to A. The only difference between Hyb0 and Hyb1 occurs if the protocol produces an incorrect evaluation. As established in the correctness analysis, the probability is statistically negligible. Thus, the views in Hyb0 and Hyb1 are statistically indistinguishable. • Hyb2 : This hybrid behaves identically to Hyb1 , except that instead of passing the honest sender’s queries to FOPPRF (Step 3), Sim R receives the programmed points {(𝑘 ∥𝑟ˆ𝑘,𝑡 , 𝑠ˆ𝑘 )}𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] from A, samples a random function 𝐹 ′ such that 𝐹 ′ (𝑘 ∥𝑟ˆ𝑘,𝑡 ) = ′ 𝑠ˆ𝑘 for 𝑘 ∈ [𝑑], 𝑡 ∈ [𝑢 ′ ] and returns O 𝐹 to A. Since Hyb1 ′ 𝐹 also returns O according to these programmed points, the views in Hyb1 and Hyb2 are perfectly identical. • Hyb3 : This hybrid behaves identically to Hyb2 , except that instead of passing the honest sender’s programmed points to FOPPRF (Step 2), Sim R receives A’s queries {𝑘 ∥𝑤˜ 𝑘,𝑡 }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] and returns uniformly random values {𝑟ˆ𝑘,𝑡 }𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] ← F2ℓ1 to A. In Hyb2 , A receives either the sender’s payload 𝑟𝑘 or a random function evaluation. Because the honest sender samples {𝑟𝑘 }𝑘 ∈ [𝑑 ] ← F2ℓ1 uniformly at random, every returned evaluation is uniformly distributed. Thus, the views in Hyb2 and Hyb3 are perfectly identical.

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

The final hybrid Hyb3 is exactly the simulated execution of Sim R . Therefore, the simulated view is statistically indistinguishable from the real execution. □

E.2

Proof of Theorem 5.2

Proof. We first establish the correctness of the protocol, and then construct simulators to demonstrate that the simulated execution is perfectly indistinguishable from the real-world protocol execution. Correctness. The correctness of the protocol relies on accurately extracting the Most Significant Bit (MSB) of the terms 𝛿 − (𝑞𝑘 −𝑤𝑘 ) and 𝛿 + (𝑞𝑘 − 𝑤𝑘 ). Assuming the inputs 𝑞𝑘 , 𝑤𝑘 , and the threshold 𝛿 are strictly bounded by 𝑧, the values of these two terms fall within the interval (−𝑧, 2𝑧). To prevent wrap-around in the two’s complement representation, the ring Z2ℓ must be parameterized such that ℓ ≥ log 𝑧 + 2. Under this condition, these MSBs are correctly evaluated, and the overall correctness of the protocol directly follows from the correctness of the underlying FMSB and FAND functionalities. Corrupted Sender. We construct a simulator Sim S for a semihonest corrupted sender. Given the sender’s input 𝒒, Sim S operates by running the adversary A and proceeds as follows: (1) Simulating FMSB (Step 2): After receiving 𝛿 − [𝑡𝑘 ] ℓS from A, Sim S samples uniformly random shares [𝑎𝑘 ] 1S ← Z2 for all 𝑘 ∈ [𝑑], and sends them to A. (2) Simulating FMSB (Step 3): After receiving 𝛿 + [𝑡𝑘 ] ℓS from A, Sim S samples uniformly random shares [𝑏𝑘 ] 1S ← Z2 for all 𝑘 ∈ [𝑑], and sends them to A. (3) Simulating FAND (Step 4): After receiving A’s inputs, Sim S samples a random share [𝑧] 1S ← Z2 and sends it to A. We argue the simulated view of A is identically distributed to the real execution. Since the protocol operates in the (FMSB, FAND )hybrid model, the messages received by A consist solely of its own secret shares. In the real execution, the shares {[𝑎𝑘 ] 1S }𝑘 ∈ [𝑑 ] , {[𝑏𝑘 ] 1S }𝑘 ∈ [𝑑 ] , and [𝑧] 1S are generated as uniformly random secret shares of the underlying functionality outputs. In the simulated execution, Sim S explicitly samples them from the uniform distribution over Z2 . Thus, the simulated view of A is identically distributed to its view in the real protocol. Corrupted Receiver. We then construct a simulator Sim R for a semi-honest corrupted receiver. Given the receiver’s input 𝒘 and the ideal output 𝑧 from FFMatch , Sim R runs A and proceeds as follows: (1) Simulating FMSB (Step 2): After receiving 𝛿 − [𝑡𝑘 ] ℓR from A, Sim R samples uniform random shares [𝑎𝑘 ] 1R ← Z2 for all 𝑘 ∈ [𝑑] and sends them to A. (2) Simulating FMSB (Step 3): After receiving 𝛿 + [𝑡𝑘 ] ℓR from A, Sim R samples uniform random shares [𝑏𝑘 ] 1R ← Z2 for all 𝑘 ∈ [𝑑] and sends them to A. (3) Simulating FAND (Step 4): After receiving A’s inputs, Sim R samples a random share [𝑧] 1R ← Z2 and sends it to A. (4) Simulating the final message (Step 5): Sim R computes the simulated sender’s message as [𝑧] 1S := [𝑧] 1R ⊕ 𝑧 ∈ Z2 , and sends it to A.

CCS ’26, November 15–19, 2026, The Hague, Netherlands

We argue the simulated view of A is identically distributed to the real execution. Similar to the corrupted sender case, the shares {[𝑎𝑘 ] 1R }𝑘 ∈ [𝑑 ] , {[𝑏𝑘 ] 1R }𝑘 ∈ [𝑑 ] , and [𝑧] 1R are uniformly random in both the real and simulated executions. The only constraint on the view is the final message [𝑧] 1S . In the real protocol, [𝑧] 1S is the honest sender’s share, which satisfies [𝑧] 1S ⊕ [𝑧] 1R = 𝑧. In the simulation, Sim R explicitly programs [𝑧] 1S to satisfy this exact relation using the ideal output 𝑧. Therefore, the simulated view of A and the real protocol view are perfectly identically distributed. Thus, the proof is complete. □

E.3

Proof of Theorem B.1

Proof. We first establish the correctness of the protocol, and then construct simulators to demonstrate that the simulated execution is perfectly indistinguishable from the real-world protocol execution. Correctness. The correctness of the protocol relies on accurately extracting the Most Significant Bit (MSB) of the term 𝑓 := 𝛿 𝑝 − Í 𝑝 𝑘 ∈ [𝑑 ] 𝑓𝑘 , where 𝑓𝑘 := |𝑞𝑘 − 𝑤 𝑘 | . Assuming the inputs 𝑞𝑘 , 𝑤 𝑘 and the threshold 𝛿 are bounded by 𝑧, the sum 𝑓 falls within the interval (−𝑑 · 𝑧 𝑝 , 𝑧 𝑝 ). To prevent wrap-around in the ring Z2ℓ , the ring must be parameterized such that ℓ ≥ log2 (𝑑 ·𝑧 𝑝 ) +1. Under this condition, the MSB accurately evaluates whether the distance exceeds the threshold, and the overall correctness directly follows from the correctness of the underlying FABS , FMult , and FMSB functionalities. Corrupted Sender. We construct a simulator Sim S for a semihonest corrupted sender. Given the sender’s input 𝒒, Sim S operates by running the adversary A and proceeds as follows: (1) Simulating FABS or FMult (Step 2): After receiving [𝑡𝑘 ] ℓS from A, Sim S samples uniform random shares [𝑓𝑘 ] ℓS ← Z2ℓ each all 𝑘 ∈ [𝑑] and sends them to A. (2) Simulating FMSB (Step 3): After receiving [𝑓 ] ℓS from A, Sim S samples a uniform random share [𝑧] 1S ← Z2 and sends it to A. We argue the simulated view of A is identically distributed to the real execution. In the (FABS, FMult, FMSB )-hybrid model, all intermediate values received by A are purely additive secret shares. In the real protocol, the shares {[𝑓𝑘 ] ℓS }𝑘 ∈ [𝑑 ] and [𝑧] 1S are uniformly distributed. In the simulation, Sim S explicitly samples them from the uniform distributions over Z2ℓ and Z2 , respectively. Thus, the simulated view of A is identically distributed to its view in the real protocol. Corrupted Receiver. We construct a simulator Sim R for a semihonest corrupted receiver. Given the receiver’s input 𝒘 and the ideal output 𝑧 ∈ Z2 from FFMatch , Sim R runs A and proceeds as follows: (1) Simulating FABS or FMult (Step 2): After receiving [𝑡𝑘 ] ℓR from A, Sim R samples uniform random shares [𝑓𝑘 ] ℓR ← Z2ℓ for each 𝑘 ∈ [𝑑] and sends them to A. (2) Simulating FMSB (Step 3): After receiving [𝑓 ] ℓR from A, Sim R samples a uniform random share [𝑧] 1R ← Z2 and sends it to A. (3) Simulating the final message (Step 4): Sim R computes the message as 𝑚 S := 𝑧 ⊕ [𝑧] 1R ∈ Z2 . Sim R then sends 𝑚 S to A, simulating the message (1 ⊕ [𝑧] 1S ) from the honest sender.

CCS ’26, November 15–19, 2026, The Hague, Netherlands

We argue the simulated view of A is identically distributed to the real execution. Similar to the corrupted sender case, the shares {[𝑓𝑘 ] ℓR }𝑘 ∈ [𝑑 ] and [𝑧] 1R are uniformly random in both executions. The final message 𝑚 S in the real protocol is 1⊕ [𝑧] 1S , which perfectly satisfies the output relation 𝑧 = 𝑚 S ⊕ [𝑧] 1R . In the simulation, Sim R directly constructs 𝑚 S to satisfy this exact relation using the ideal output 𝑧. Therefore, the simulated view of A and the real protocol view are perfectly identically distributed. Thus, the proof is complete. □

E.4

Proof of Theorem 6.1

Proof. We first analyze the protocol’s correctness and then prove the security of the protocol by constructing simulators for both a corrupted sender and a corrupted receiver. Correctness. We first consider the matching case, where for a sender point 𝒒 𝑗 ∈ 𝑄, there exists a receiver point 𝒘𝑖 ∈ 𝑊 such that dist𝑝 (𝒘𝑖 , 𝒒 𝑗 ) ≤ 𝛿. By the definition of spatial hashing, there must exist a unique index ℎ ∗ ∈ [2𝑑 ] such that the computed cell identifiers match: C𝒘𝑖 ,ℎ∗ = C𝒒 𝑗 . By the unique center assumption, the sender’s points are sufficiently separated such that each grid cell contains at most one sender point. Consequently, the Cuckoo hash table 𝑇𝑞 is successfully constructed with overwhelming probability. Let 𝑗 ∗ denote the bin index of the tuple (C𝒒 𝑗 , 𝒒 𝑗 ) in 𝑇𝑞 . Because both parties use identical hash functions, the receiver’s corresponding tuple (C𝒘𝑖 ,ℎ∗ , 𝒘𝑖 ) is mapped to the same bin index 𝑇𝑤 [ 𝑗 ∗ ]. By the unique ball assumption, a cell intersects at most one 𝛿-radius receiver ball. Thus, the cell identifiers C𝒘𝑖 ,ℎ are unique for all 𝑖 ∈ [𝑛], ℎ ∈ [2𝑑 ], ensuring no key collisions exist within the programmed sets {𝐿 𝑗 } 𝑗 ∈ [𝑚 ′ ] provided to FOPPRF . By the correctness of FOPPRF , the sender queries with (C𝒒 𝑗 ∥𝜏) from 𝑇𝑞 [ 𝑗 ∗ ] and successfully learns the programmed payload:
𝑠ˆ𝑗 ∗ ∥ 𝒓ˆ 𝑗 ∗ = 𝑠 𝑗 ∗ ∥ shift ⌈log 6𝛿 ⌉ (𝒘𝑖 , C𝒘𝑖 ,ℎ∗ − 2𝛿) − 𝒓 𝑗 ∗ mod 2ℓ2 . Meanwhile, the receiver holds 𝑠 𝑗 ∗ and 𝒓 𝑗 ∗ for the 𝑗 ∗ -th bin of 𝑇𝑤 . To ensure that the computation will not overflow in OT-based fuzzy matching, we set the bit length ℓ2 according to the analysis in Appendix E.2 and Appendix E.3. Given that the input is less than 6𝛿 in the reduced domain, we set ℓ2 := ⌈log(6𝛿)⌉ + 2 for 𝐿∞ distance and ℓ2 := ⌈log 𝑑 (6𝛿) 𝑝 ⌉ + 1 for 𝐿𝑝 distance. Note that for 𝐿2 distance, ℓ2 can be further optimized to ⌈log 𝑑 (3𝛿) 2 ⌉, according to the fact that if the cell of 𝒒 𝑗 and 𝒘𝑖 ’s ball is matched then |𝑞 𝑗,𝑘 − 𝑤𝑖,𝑘 | < 3𝛿 for all 𝑘 ∈ [𝑑]. Finally, by the correctness of the functionalities FssFMatch , FssPEQT , FAND , FPerm , and FOT , the receiver R correctly obtains 𝒒 𝑗 . We next consider the mismatch case, where for a sender point 𝒒 𝑗 ∈ 𝑄, it holds that dist𝑝 (𝒘𝑖 , 𝒒 𝑗 ) > 𝛿 for all 𝒘𝑖 ∈ 𝑊 . Let 𝑗 ∗ denote its bin index in 𝑇𝑞 . We distinguish two sub-cases: Case 1 (Cell Collision, Distance Mismatch): There exists a 𝒘𝑖 ∈ 𝑊 and ℎ ∗ ∈ [2𝑑 ] such that C𝒘𝑖 ,ℎ∗ = C𝒒 𝑗 . Because the distance strictly exceeds 𝛿, the correctness of FssFMatch ensures the reconstructed output is 𝜈 𝑗 ∗ = 0. Case 2 (No Cell Collision): For all 𝒘𝑖 ∈ 𝑊 and ℎ ∈ [2𝑑 ], C𝒘𝑖 ,ℎ ≠ C𝒒 𝑗 . The sender’s query to FOPPRF is unprogrammed, yielding a uniformly random value 𝑠ˆ𝑗 ∗ ∈ F2ℓ1 . The probability of an accidental collision 𝑠ˆ𝑗 ∗ = 𝑠 𝑗 ∗ is 2−ℓ1 . Setting ℓ1 := 𝜆 + log 𝑚 ′ ensures that by a union bound, the probability of any such collision across all 𝑚 ′ bins is bounded by 2−𝜆 . Thus, except with negligible

Meng Hao et al.

probability, FssPEQT correctly ensures the reconstructed output is 𝜇 𝑗 ∗ = 0. In both sub-cases, the FAND functionality produces shares of 0, and the final FOT delivers ⊥ to the receiver. This completes the correctness proof. Corrupted Sender. We construct a simulator Sim S for a semihonest corrupted sender. Given the sender’s input 𝑄, Sim S runs the adversary A and proceeds as follows: (1) Simulating FOPPRF (Step 5): After receiving the queries, Sim S samples uniformly random values 𝑠ˆ𝑗 ← F2ℓ1 and 𝒓ˆ 𝑗 ← Z𝑑2ℓ2 for all 𝑗 ∈ [𝑚 ′ ], and returns {ˆ𝑠 𝑗 ∥ 𝒓ˆ 𝑗 } 𝑗 ∈ [𝑚 ′ ] to A. (2) Simulating FssFMatch , FssPEQT , and FAND (Steps 6-8): After receiving A’s inputs to these functionalities, Sim S simulates the outputs by sampling uniformly random bits 𝜈 𝑗S , 𝜇 𝑗S , 𝑏 𝑗S ← F2 for all 𝑗 ∈ [𝑚 ′ ] and returns them to A. (3) Simulating FPerm (Step 9): After receiving {𝑏 𝑗S } 𝑗 ∈ [𝑚 ′ ] from A, Sim S samples a random permutation 𝜋 over [𝑚 ′ ] and returns it to A. (4) Simulating FOT (Step 10): After receiving OT’s inputs from A, Sim S provides no output to A. We demonstrate the security of the simulation through a sequence of hybrid games: • Hyb0 : The real protocol execution in the hybrid model. • Hyb1 : This hybrid behaves identically to Hyb0 , except that instead of invoking FPerm (Step 9) and FOT (Step 10), Sim S returns a random permutation 𝜋 over [𝑚 ′ ] as the output of FPerm , and provides no output for A in FOT , which perfectly simulates the functionalities’ behavior. Thus, the views in Hyb0 and Hyb1 are perfectly identical. • Hyb2 : This hybrid behaves identically to Hyb1 except the simulation of FssFMatch , FssPEQT , and FAND (Steps 6-8). Sim S receives A’s inputs and simply returns uniformly random bits 𝜈 𝑗S , 𝜇 𝑗S , 𝑏 𝑗S ← F2 for all 𝑗 ∈ [𝑚 ′ ]. Because these ideal functionalities output uniform secret shares to A in Hyb1 , the views in Hyb1 and Hyb2 are perfectly identical. • Hyb3 : This hybrid behaves identically to Hyb2 , except that instead of passing the honest receiver’s programmed points to FOPPRF (Step 5), Sim R receives A’s queries and returns uniformly random values 𝑠ˆ𝑗 ← F2ℓ1 and 𝒓ˆ 𝑗 ← Z𝑑2ℓ2 for all 𝑗 ∈ [𝑚 ′ ]. In Hyb2 , if a valid spatial match occurs, 𝒓ˆ 𝑗 is masked by the receiver’s uniformly random value 𝒓 𝑗 , making it uniformly distributed. If no match occurs, it is a random function evaluation. The case of 𝑠ˆ𝑗 is similar. Because the honest receiver samples all 𝑠 𝑗 and 𝒓 𝑗 uniformly at random, every evaluation A receives in Hyb2 is perfectly uniform and independent of A’s input. Thus, the views in Hyb2 and Hyb3 are perfectly identical. The final hybrid Hyb3 is exactly the simulated execution of Sim S . Therefore, the simulated view is perfectly indistinguishable from the real execution. Corrupted Receiver. We construct a simulator Sim R for a semi-honest corrupted receiver. Given the receiver’s input 𝑊 and the ideal output set 𝑍 from FFPSI , Sim R runs A and proceeds as follows:

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

(1) Simulating FOPPRF (Step 5): After receiving the programmed points {𝐿 𝑗 } 𝑗 ∈ [𝑚 ′ ] from A, Sim R samples a random function 𝐹 programmed on {𝐿 𝑗 } 𝑗 ∈ [𝑚 ′ ] . Sim R sends O 𝐹 to A. (2) Simulating FssFMatch , FssPEQT , and FAND (Steps 6-8): After receiving A’s inputs, Sim R samples uniformly random bits 𝜈 𝑗R , 𝜇 𝑗R , 𝑏 𝑗R ← F2 for all 𝑗 ∈ [𝑚 ′ ] and returns them to A. (3) Simulating FPerm and FOT (Steps 9-10): To simulate the final delivery of the intersection, Sim R pads the ideal output set 𝑍 with ⊥ elements until it contains exactly 𝑚 ′ items. Sim R shuffles this padded set randomly to yield {𝑧 𝑗 } 𝑗 ∈ [𝑚 ′ ] . For each 𝑗 ∈ [𝑚 ′ ], Sim R defines 𝑏ˆ 𝑗 := 0 if 𝑧 𝑗 = ⊥, and 𝑏ˆ 𝑗 := 1 otherwise. After receiving A’s inputs, Sim R returns {𝑏ˆ 𝑗 } 𝑗 ∈ [𝑚 ′ ] as the output of FPerm and {𝑧 𝑗 } 𝑗 ∈ [𝑚 ′ ] as the output of the final FOT . We demonstrate the security of the simulation through a sequence of hybrid games: • Hyb0 : This is the real protocol execution. • Hyb1 : This hybrid behaves identically to Hyb0 except the simulation of FPerm and FOT (Steps 9-10). Sim R pads the ideal output set 𝑍 with ⊥ elements until it contains exactly 𝑚 ′ items. It then randomly shuffles this padded set to yield {𝑧 𝑗 } 𝑗 ∈ [𝑚 ′ ] . For each 𝑗 ∈ [𝑚 ′ ], Sim R defines 𝑏ˆ 𝑗 := 1 if 𝑧 𝑗 ≠ ⊥, and 𝑏ˆ 𝑗 := 0 otherwise. It returns {𝑏ˆ 𝑗 } 𝑗 ∈ [𝑚 ′ ] as the output of FPerm and {𝑧 𝑗 } 𝑗 ∈ [𝑚 ′ ] as the output of FOT . In Hyb0 , FPerm applies a uniformly random permutation to the underlying match bits, and FOT returns the corresponding intersection elements interspersed with ⊥s. Because the permutation is uniformly random and completely hidden from A, the sequence of bits and retrieved payloads is simply a uniformly random arrangement of exactly |𝑍 | matches and 𝑚 ′ − |𝑍 | ⊥s. The only difference between Hyb0 and Hyb1 occurs if the protocol produces an incorrect evaluation. As established in the correctness analysis, the probability is statistically negligible. Thus, the views in Hyb0 and Hyb1 are statistically indistinguishable. • Hyb2 : This hybrid behaves identically to Hyb1 except the simulation of FssFMatch , FssPEQT , and FAND (Steps 6-8). Sim R receives A’s inputs to these functionalities and returns uniformly random bits 𝜈 𝑗R , 𝜇 𝑗R , 𝑏 𝑗R ← F2 for all 𝑗 ∈ [𝑚 ′ ]. In Steps 6-8, the intermediate values 𝜈 𝑗R , 𝜇 𝑗R , 𝑏 𝑗R are uniform secret shares in Hyb1 , which Sim R correctly models by sampling uniformly. Thus, the views in Hyb1 and Hyb2 are perfectly identical. • Hyb3 : This hybrid behaves identically to Hyb2 except the simulation of FOPPRF (Step 5). After receiving the programmed points {𝐿 𝑗 } 𝑗 ∈ [𝑚 ′ ] from A, Sim R samples a random function 𝐹 programmed on {𝐿 𝑗 } 𝑗 ∈ [𝑚 ′ ] . Sim R sends O 𝐹 to A. Since Hyb2 also returns O 𝐹 according to these programmed points, the views in Hyb2 and Hyb3 are perfectly identical. The final hybrid Hyb3 is exactly the simulated execution of Sim R . Therefore, the simulated view is statistically indistinguishable from the real execution. □

CCS ’26, November 15–19, 2026, The Hague, Netherlands

E.5

Proof of Theorem 7.2

Proof. We first analyze the protocol’s correctness and then prove the security of the protocol by constructing simulators for both a corrupted sender and a corrupted receiver. Correctness. Before analyzing correctness for different cases, we illustrate the distinctness of programmed points in two invocations of OPPRF. Below, we consider any dimension 𝑘 ∈ [𝑑]. (1) In the first OPPRF invocation, the globally disjoint assumption of the sender set ensures that for any 𝑗, 𝑗 ′ ∈ [𝑚], [𝑞 𝑗,𝑘 − 𝛿, 𝑞 𝑗,𝑘 + 𝛿] ∩ [𝑞 𝑗 ′ ,𝑘 − 𝛿, 𝑞 𝑗 ′ ,𝑘 + 𝛿] = ∅ and hence |𝑞 𝑗,𝑘 − 𝑞 𝑗 ′ ,𝑘 | > 2𝛿. By Corollary 3.2, this implies the intersection of their prefixes is empty: {𝑞˜ 𝑗,𝑘,𝑡 }𝑡 ∈ [𝑢 ] ∩ {𝑞˜ 𝑗 ′ ,𝑘,𝑡 }𝑡 ∈ [𝑢 ] = ∅. Therefore, all programmed points {𝑞˜ 𝑗,𝑘,𝑡 } 𝑗 ∈ [𝑚],𝑡 ∈ [𝑢 ] of the first OPPRF are distinct. (2) In the second OPPRF invocation, the globally disjoint assumption of the receiver set ensures that for any 𝑖, 𝑖 ′ ∈ [𝑛], [𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 + 𝛿] ∩ [𝑤𝑖 ′ ,𝑘 − 𝛿, 𝑤𝑖 ′ ,𝑘 + 𝛿] = ∅ and hence |𝑤𝑖,𝑘 − 𝑤𝑖 ′ ,𝑘 | > 2𝛿. By Corollary 3.3, this implies the intersection of their prefixes is empty: {𝑤˜ 𝑖,𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] ∩ {𝑤˜ 𝑖 ′ ,𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] = ∅. Moreover, by Corollary 3.4, for each sender prefix set {𝑞˜ 𝑗,𝑘,𝑡 }𝑡 ∈ [𝑢 ] , there is at most one receiver prefix set {𝑤˜ 𝑖,𝑘,𝑡 }𝑡 ∈ [𝑢 ′ ] with a unique 𝑡 intersected with it. Therefore, by the correctness of the first OPPRF, {𝑟ˆ𝑖,𝑘,𝑡 }𝑖 ∈ [𝑛],𝑡 ∈ [𝑢 ′ ] are independent and uniformly random, since 𝑟ˆ𝑖,𝑘,𝑡 is either a random function value (unmatched with all programmed points) or some 𝑟 𝑗,𝑘 (matched with a point). By setting appropriate bit lengths as analyzed below, all values within the set {𝑟ˆ𝑖,𝑘,𝑡 }𝑖 ∈ [𝑛],𝑡 ∈ [𝑢 ′ ] for a given dimension 𝑘 are distinct. This ensures that all programmed points of the second OPPRF are distinct. With the correct invocations of OPPRF established, we proceed to analyze the correctness for different cases. We first consider the matching case where for a sender point 𝒒 𝑗 ∈ 𝑄, there exists 𝒘𝑖 ∈ 𝑊 such that dist∞ (𝒘𝑖 , 𝒒 𝑗 ) ≤ 𝛿. This implies that 𝑤𝑖,𝑘 ∈ [𝑞 𝑗,𝑘 − 𝛿, 𝑞 𝑗,𝑘 + 𝛿] for all dimensions 𝑘 ∈ [𝑑]. By Theorem 3.1, for each dimension 𝑘 ∈ [𝑑], there exists a unique index 𝑡𝑘∗ ∈ [𝑢 ′ ] such that 𝑤˜ 𝑖,𝑘,𝑡 ∗ ∈ {𝑞˜ 𝑗,𝑘,𝑡 }𝑡 ∈ [𝑢 ] . By the correctness of the 𝑘 first FOPPRF , the receiver successfully learns 𝑟ˆ𝑖,𝑘,𝑡 ∗ = 𝑟 𝑗,𝑘 . Similarly, 𝑘 by the correctness of the second FOPPRF , the sender learns 𝑠 𝑗,𝑘 = 𝑠ˆ𝑖,𝑘 . This results in the aggregate sums matching 𝑠 𝑗 = 𝑠ˆ𝑖 . Finally, by the correctness of FwLPSI , the receiver queries 𝑠ˆ𝑖 , and successfully obtains 𝑠 𝑗 and the associated payload 𝒒 𝑗 . We next consider the mismatch case, where for a sender point 𝒒 𝑗 ∈ 𝑄, it holds that dist∞ (𝒘𝑖 , 𝒒 𝑗 ) > 𝛿 for all 𝒘𝑖 ∈ 𝑊 . This yields that for any 𝒘𝑖 , there exists at least one dimension 𝑘 ∗ such that 𝑤𝑖,𝑘 ∗ ∉ [𝑞 𝑗,𝑘 ∗ − 𝛿, 𝑞 𝑗,𝑘 ∗ + 𝛿]. By Theorem 3.1, this implies that the intersection of their prefixes is empty: {𝑞˜ 𝑗,𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ] ∩ {𝑤˜ 𝑖,𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] = ∅. By the correctness of the first FOPPRF , all evaluations {𝑟ˆ𝑖,𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] obtained by the receiver are uniformly random and are independent of 𝑟 𝑗,𝑘 ∗ . To ensure correctness of the entire protocol, we must guarantee two conditions: (1) no random function evaluation {𝑟ˆ𝑖,𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] accidentally collides with any of the sender’s payloads 𝑟 𝑗,𝑘 ∗ (preventing false positives), and (2) all values within the set {𝑟ˆ𝑖,𝑘 ∗ ,𝑡 }𝑖 ∈ [𝑛],𝑡 ∈ [𝑢 ′ ] are strictly distinct, ensuring the receiver does not provide duplicate keys when programming the second FOPPRF . Considering the execution of OPPRF on the two sets, the total number of points drawn in each dimension is bounded by (𝑛𝑢 ′ + 𝑚). The probability of any collision occurring among these points is bounded by (𝑛𝑢 ′ + 𝑚) 2 /2ℓ1 . Considering all

CCS ’26, November 15–19, 2026, The Hague, Netherlands

𝑑 dimensions, setting ℓ1 := 𝜆 + 2 log(𝑛𝑢 ′ + 𝑚) + log 𝑑 ensures the probability of a collision is bounded by 1/2𝜆 , which is negligible. Therefore, 𝑟 𝑗,𝑘 ∗ ∉ {𝑟ˆ𝑖,𝑘 ∗ ,𝑡 }𝑡 ∈ [𝑢 ′ ] with overwhelming probability. Under the above condition, by the correctness of the second FOPPRF , the sender receives a uniformly random 𝑠 𝑗,𝑘 ∗ , independent to 𝑠ˆ𝑖,𝑘 ∗ , since 𝑠 𝑗,𝑘 ∗ is either a random value (unmatched with all programmed points) or some other 𝑠ˆ𝑖 ′ ,𝑘 ∗ (matched with a point from 𝑟ˆ𝑖 ′ ,𝑘 ∗ ,𝑡 ). Because dimensions are evaluated independently, and because for each 𝑖 ∈ [𝑛], there exists 𝑘 ∗ such that 𝑠 𝑗,𝑘 ∗ and 𝑠ˆ𝑖,𝑘 ∗ are uniformly random and independent, the aggregate sums 𝑠 𝑗 and 𝑠ˆ𝑖 are uniformly random and independent. Setting ℓ2 := 𝜆 + log 𝑚 + log 𝑛 guarantees that the probability of an accidental collision 𝑠 𝑗 = 𝑠ˆ𝑖 across all 𝑚 × 𝑛 possible pairs is bounded by (𝑚𝑛)/2ℓ2 ≤ 1/2𝜆 . Thus, the FwLPSI query fails, returning nothing for this mismatch, completing the correctness proof. Corrupted Sender. We construct a simulator Sim S for a semihonest corrupted sender. Given the sender’s input 𝑄, Sim S runs the adversary A and proceeds as follows: (1) Simulating FOPPRF (Step 3): Sim S receives the programmed points {(𝑘 ∥𝑞˜ 𝑗,𝑘,𝑡 , 𝑟 𝑗,𝑘 )} 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ] generated by A. Sim S samples a random function 𝐹 such that 𝐹 (𝑘 ∥𝑞˜ 𝑗,𝑘,𝑡 ) = 𝑟 𝑗,𝑘 for 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], 𝑡 ∈ [𝑢], and returns O 𝐹 to A. (2) Simulating FOPPRF (Step 4): After receiving the A’s queries {𝑘 ∥𝑟 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] , Sim S samples uniformly random values 𝑠 𝑗,𝑘 ← F2ℓ2 for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], and sends them to A. (3) Simulating FwLPSI (Step 6): After receiving {(𝑠 𝑗 , 𝒒 𝑗 )} 𝑗 ∈ [𝑚] , Sim S returns nothing. We demonstrate the security of the simulation through a sequence of hybrid games:

Meng Hao et al.

Corrupted Receiver. We construct a simulator Sim R for a semihonest corrupted receiver. Given the receiver’s input 𝑊 and the ideal output set 𝑍 from FFPSI , Sim R runs A and proceeds as follows: (1) Simulating FOPPRF (Step 3): After receiving the A’s queries {𝑘 ∥𝑤˜ 𝑖,𝑘,𝑡 }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] , Sim R samples uniformly random values {𝑟ˆ𝑖,𝑘,𝑡 }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] , and returns them to A. (2) Simulating FOPPRF (Step 4): After receiving the programmed points {(𝑘 ∥𝑟ˆ𝑖,𝑘,𝑡 , 𝑠ˆ𝑖,𝑘 )}𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] from A, Sim R samples a random function 𝐹 ′ such that 𝐹 ′ (𝑘 ∥𝑟ˆ𝑖,𝑘,𝑡 ) = 𝑠ˆ𝑖,𝑘 for ′ 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], 𝑡 ∈ [𝑢 ′ ]. Sim R returns O 𝐹 to A. (3) Simulating FwLPSI (Step 6): After receiving A’s input {ˆ𝑠𝑖 }𝑖 ∈ [𝑛] , for every point 𝒒 𝑗 ∈ 𝑍 , Sim R identifies unique 𝑖 ∗ ∈ [𝑛] such that dist∞ (𝒘𝑖 ∗ , 𝒒 𝑗 ) ≤ 𝛿. Sim R constructs the output set 𝐼 := {(𝑠ˆ𝑖 ∗ , 𝒒 𝑗 ) | 𝒒 𝑗 ∈ 𝑍 } and returns 𝐼 to A. We demonstrate the security of the simulation through a sequence of hybrid games: • Hyb0 : This is the real protocol execution. • Hyb1 : This hybrid behaves identically to Hyb0 except the simulation of FwLPSI (Step 6). After receiving A’s input {ˆ𝑠𝑖 }𝑖 ∈ [𝑛] , for each 𝒒 𝑗 ∈ 𝑍 , Sim R identifies the unique 𝑖 ∗ ∈ [𝑛] such that dist∞ (𝒘𝑖 ∗ , 𝒒 𝑗 ) ≤ 𝛿. This uniqueness is guaranteed by the globally disjoint assumption. Sim R constructs the output set 𝐼 := {(𝑠ˆ𝑖 ∗ , 𝒒 𝑗 ) | 𝒒 𝑗 ∈ 𝑍 }, and returns 𝐼 to A. The only difference between Hyb0 and Hyb1 occurs if the protocol produces an incorrect evaluation. As established in the correctness analysis, the probability is statistically negligible. Thus, the views in Hyb0 and Hyb1 are statistically indistinguishable. • Hyb2 : This hybrid behaves identically to Hyb1 except that instead of invoking FOPPRF (Step 4), after receiving the programmed points {(𝑘 ∥𝑟ˆ𝑖,𝑘,𝑡 , 𝑠ˆ𝑖,𝑘 )}𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] from A, Sim R samples a random function 𝐹 ′ such that 𝐹 ′ (𝑘 ∥𝑟ˆ𝑖,𝑘,𝑡 ) = 𝑠ˆ𝑖,𝑘 for ′ 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], 𝑡 ∈ [𝑢 ′ ] and returns O 𝐹 to A. Since Hyb1 ′ 𝐹 also returns O according to these programmed points, the views in Hyb1 and Hyb2 are perfectly identical. • Hyb3 : This hybrid behaves identically to Hyb2 , except that instead of passing the honest sender’s points to FOPPRF (Step 3), Sim R receives A’s queries {𝑘 ∥𝑤˜ 𝑖,𝑘,𝑡 }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] and returns uniformly random values {𝑟ˆ𝑖,𝑘,𝑡 }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ′ ] ← F2ℓ1 . As illustrated in the correctness analysis, in Hyb2 , A receives either the sender’s payload 𝑟 𝑗,𝑘 or a random function evaluation. Because the honest sender samples 𝑟 𝑗,𝑘 ← F2ℓ1 uniformly at random, every returned evaluation is uniformly distributed. Thus, the views in Hyb2 and Hyb3 are perfectly identical.

• Hyb0 : This is the real protocol execution. • Hyb1 : This hybrid behaves identically to Hyb0 , except that instead of invoking FwLPSI (Step 6), Sim S receives {(𝑠 𝑗 , 𝒒 𝑗 )} 𝑗 ∈ [𝑚] from A and returns nothing, which perfectly simulates the FwLPSI ’s behavior. Thus, the views in Hyb0 and Hyb1 are perfectly identical. • Hyb2 : This hybrid behaves identically to Hyb1 , except that instead of passing the honest receiver’s programmed points to FOPPRF (Step 4), Sim S directly returns uniformly random values {𝑠 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] ← F2ℓ2 to A. In Hyb1 , as illustrated in the correctness analysis, 𝑠 𝑗,𝑘 is either equal to the receiver’s choice 𝑠ˆ𝑖,𝑘 or a random function output. Because the honest receiver samples 𝑠ˆ𝑖,𝑘 ← F2ℓ2 uniformly at random, every 𝑠 𝑗,𝑘 in Hyb1 is perfectly uniform and independent of A’s view. Thus, the views in Hyb1 and Hyb2 are perfectly identical. The final hybrid Hyb3 is exactly the simulated execution of Sim R . • Hyb3 : This hybrid behaves identically to Hyb2 , except that inTherefore, the simulated view is statistically indistinguishable from stead of passing honest receiver’s queries to FOPPRF (Step 3), the real execution. Sim S receives the programmed points {(𝑘 ∥𝑞˜ 𝑗,𝑘,𝑡 , 𝑟 𝑗,𝑘 )} 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑡 ∈ [𝑢 ] □ from A, samples a random function 𝐹 such that 𝐹 (𝑘 ∥𝑞˜ 𝑗,𝑘,𝑡 ) = 𝑟 𝑗,𝑘 for 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], 𝑡 ∈ [𝑢], and sends O 𝐹 to A. Since E.6 Proof of Theorem 7.3 Hyb2 also returns O 𝐹 according to these programmed points, Proof. The correctness of the protocol is directly derived from the views in Hyb2 and Hyb3 are perfectly identical. the correctness of the 𝐿∞ protocol for high-dimensional sets and The final hybrid Hyb3 is exactly the simulated execution of Sim S . the low-dimensional protocol, and hence we omit it here. Below, we Therefore, the simulated view is perfectly indistinguishable from mainly prove the security of the protocol by constructing simulators the real execution. for both a corrupted sender and a corrupted receiver.

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

Corrupted Sender. We construct a simulator Sim S for a semihonest corrupted sender. Given the sender’s input 𝑄, Sim S runs the adversary A and proceeds as follows: (1) Simulating fuzzy mapping (Step 1): Sim S invokes the simu∞ lator for the corrupted sender in the Π𝐿FPSI-high protocol and sends the resulting transcript to A. (2) Simulating FOPPRF (Step 5): After receiving the programmed points {𝐿𝑖 }𝑖 ∈ [𝑛′ ] from A, Sim S samples a random function 𝐺 programmed on {𝐿𝑖 }𝑖 ∈ [𝑛′ ] . Sim S sends O𝐺 to A. (3) Simulating FFMatch and FOT (Steps 6-7): Sim S receives its shares 𝒈𝑖 to FFMatch and (⊥, 𝒈𝑖 ) to FOT from A, and returns nothing. We demonstrate the security of the simulation through a sequence of hybrid games: • Hyb0 : This is the real protocol execution. • Hyb1 : This hybrid behaves identically to Hyb0 except the simulation of FFMatch and FOT (Steps 6-7). Sim S receives A’s inputs 𝒈𝑖 to FFMatch and (⊥, 𝒈𝑖 ) to FOT and returns nothing, which perfectly simulates the functionalities’ behavior. Thus, the views in Hyb0 and Hyb1 are perfectly identical. • Hyb2 : This hybrid behaves identically to Hyb2 except the simulation of FOPPRF (Step 5). After receiving the programmed points {𝐿𝑖 }𝑖 ∈ [𝑛′ ] from A, Sim S samples a random function 𝐹 programmed on {𝐿𝑖 }𝑖 ∈ [𝑛′ ] . Sim S sends O𝐺 to A. Since Hyb1 also returns O𝐺 according to these programmed points, the views in Hyb1 and Hyb2 are perfectly identical. • Hyb3 : This hybrid behaves identically to Hyb2 , except that ∞ Sim R invokes the receiver simulator for the Π𝐿FPSI-high protocol and sends the transcript to A. The perfect indistinguishability of the views in Hyb2 and Hyb3 follows from the security of the 𝐿∞ protocol. The final hybrid Hyb3 is exactly the simulated execution of Sim S . Therefore, the simulated view is perfectly indistinguishable from the real execution. Corrupted Receiver. We construct a simulator Sim R for a semihonest corrupted receiver. Given the receiver’s input 𝑊 and the ideal output set 𝑍 from FFPSI , Sim R runs A and proceeds as follows: (1) Simulating fuzzy mapping (Step 1): Sim R invokes the sim∞ ulator for the corrupted receiver in the Π𝐿FPSI-high protocol, purposefully omitting the final intersection delivery. Sim R sends the transcript to A (2) Simulating FOPPRF (Step 5): After receiving queries from A, Sim R samples uniformly random values 𝒈ˆ𝑖 ← Z𝑑ℓ ′ for all 2 𝑖 ∈ [𝑛 ′ ] and returns them to A. (3) Simulating FFMatch and FOT (Steps 6-7): For each bin 𝑖 ∈ [𝑛 ′ ], Sim R identifies if there are a mapped element 𝑇𝑤 [𝑖] = (id𝒘𝑖 ∥𝜏, 𝒘𝑖 ) and a 𝒒 ∈ 𝑍 such that dist𝑝 (𝒒, 𝒘𝑖 ) ≤ 𝛿. If such a match exists, Sim R sets the simulated match bit 𝑏𝑖 := 1 and ′ constructs the OT payload as 𝒛𝑖 := 𝒒 − 𝒈ˆ𝑖 mod 2ℓ . Otherwise (or if the bin is empty), Sim R sets 𝑏𝑖 := 0 and 𝒛𝑖 := ⊥. After receving A’s inputs, Sim R returns {𝑏𝑖 }𝑖 ∈ [𝑛′ ] and {𝒛𝑖 }𝑖 ∈ [𝑛′ ] to A as the outputs of the functionalities. We demonstrate the security of the simulation through a sequence of hybrid games: • Hyb0 : This is the real protocol execution.

CCS ’26, November 15–19, 2026, The Hague, Netherlands

• Hyb1 : This hybrid behaves identically to Hyb0 except the simulation of FFMatch and FOT (Steps 6-7). For each bin 𝑖 ∈ [𝑛 ′ ], if 𝑇𝑤 [𝑖] = (id𝒘𝑖 ∥𝜏, 𝒘𝑖 ), Sim R checks if there exists an ideal match 𝒒 ∈ 𝑍 such that dist𝑝 (𝒒, 𝒘𝑖 ) ≤ 𝛿. By the globally disjoint assumption, 𝒘𝑖 can match at most one 𝒒 ∈ 𝑍 , meaning this check is unambiguous. If a match exists, Sim R sets the simulated match bit 𝑏𝑖 := 1 and constructs the OT payload ′ as 𝒛𝑖 := 𝒒 − 𝒈ˆ𝑖 mod 2ℓ . Otherwise, Sim R sets 𝑏𝑖 := 0 and 𝒛𝑖 := ⊥. Sim R returns {𝑏𝑖 } ∈ [𝑛′ ] and {𝒛𝑖 } ∈ [𝑛′ ] to A. In Hyb0 , if 𝑏𝑖 = 1, A obtains the sender’s mask 𝒈𝑖 from FOT . In the simulation, setting 𝒛𝑖 := 𝒒 − 𝒈ˆ𝑖 implicitly defines 𝒛𝑖 = 𝒈𝑖 , perfectly mimicking the relationship between the FOPPRF uniform masks and the FOT payloads while embedding the true ideal intersection 𝑍 . The only difference between Hyb0 and Hyb1 occurs if the protocol produces an incorrect evaluation that is statistically negligible. Thus, the views in Hyb0 and Hyb1 are statistically indistinguishable. • Hyb2 : This hybrid behaves identically to Hyb1 , except that instead of passing the honest sender’s programmed points to FOPPRF (Step 5), Sim R returns uniformly random values 𝒈ˆ𝑖 ← Z𝑑ℓ ′ for all 𝑖 ∈ [𝑛 ′ ]. In Hyb1 , A receives 𝒈ˆ𝑖 = 2

′

𝒒 𝑗 − 𝒈𝑖 mod 2ℓ if the identifiers match, or a random function output otherwise. Because the honest sender samples 𝒈𝑖 ← Z𝑑ℓ ′ uniformly at random, the masked value 𝒒 𝑗 − 𝒈𝑖 is 2 perfectly uniform and independent of 𝒒 𝑗 . Thus, all outputs received by A in Hyb1 are uniformly distributed. Thus, the views in Hyb1 and Hyb2 are perfectly identical. • Hyb3 : This hybrid behaves identically to Hyb2 , except that ∞ Sim R invokes the receiver simulator for the Π𝐿FPSI-high protocol, purposefully omitting the final intersection delivery. Sim R sends the transcript to A. The perfect indistinguishability of the views in Hyb2 and Hyb3 follows from the security of the 𝐿∞ protocol. The final hybrid Hyb3 is exactly the simulated execution of Sim R . Therefore, the simulated view is statistically indistinguishable from the real execution. □

Related documents

• Efficient Fuzzy PSI under One-Sided Assumptions#1083166
• OMP-MoE: Efficient Expert Pruning for Mixture-of-Experts LLMs via Orthogonal Matching Pursuit#1115587
• Emergent Gauge Symmetries on the Fuzzy Sphere#450360
• Partial Stabilizer Learning under Fixed Commuting Constraints and the Absence of a Copy-Rate Discount#1083415
• xDup: Privacy-Preserving Deduplication for Humanitarian Organizations using Fuzzy PSI#2451