ARTIFACT EVALUATED
ARTIFACT EVALUATED
ARTIFACT EVALUATED
AVAILABLE
FUNCTIONAL
REPRODUCED
Efficient Fuzzy Private Set Intersection from Secret-shared OPRF Xinpeng Yang1 , Meng Hao2* , Chenkai Weng3 , Robert H. Deng2 , Yonggang Wen1 , Tianwei Zhang1
arXiv:2604.14909v1 [cs.CR] 16 Apr 2026
1
Nanyang Technological University, [email protected], {ygwen, tianwei.zhang}@ntu.edu.sg 2 Singapore Management University, [email protected], [email protected] 3 Arizona State University, [email protected]
Abstract—Private set intersection (PSI) enables a sender holding a set Q of size m and a receiver holding a set W of size n to securely compute the intersection Q ∩ W . Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items q ∈ Q for which there exists some w ∈ W satisfying dist(q, w) ≤ δ under a given distance metric. Although several FPSI works are proposed for Lp distance metrics with p ∈ [1, ∞], they either heavily rely on expensive homomorphic encryptions, or incur undesirable complexity, e.g., exponential to the element dimension, both of which lead to poor practical efficiency. In this work, we propose efficient FPSI protocols for Lp∈[1,∞] distance metrics, primarily leveraging significantly cheaper symmetric-key operations. Our protocols achieve linear communication and computation complexity in the set sizes m, n, the dimension d, and the distance threshold δ . Our core building block is an oblivious programmable PRF with secret-shared outputs, which may be of independent interest. Furthermore, we incorporate a prefix technique that reduces the dependence on the distance threshold δ to logarithmic, which is particularly suitable for large δ . We implement our FPSI protocols and compare them with state-of-the-art constructions. Experimental results demonstrate that our protocols consistently and significantly outperform existing works across all settings. Specifically, our protocols achieve a speedup of 12∼145× in running time and a reduction of 3∼8× in communication cost compared to Gao et al. (ASIACRYPT’24) and a speedup of 9∼80× in running time and a reduction of 5∼19× in communication cost compared to Dang et al. (CCS’25).
1. Introduction Private set intersection (PSI) [1], [2], [3], [4], [5], [6], [7] enables two parties, the sender and the receiver, to compute the intersection of their sets without revealing additional information beyond the intersection itself. Standard PSI protocols focus on exact matching and have been widely employed in various scenarios such as password breach monitoring and genome matching [8], [9]. However, in some complicated applications with multi-dimensional inputs, requiring exact intersection is often impractical or even impossible. For example, in biometric authentication ∗ Meng Hao is the corresponding author
systems (e.g., fingerprint or face), two samples belonging to the same individual may differ due to environmental variations and feature extraction perturbations [10], which limits the application of standard PSI protocols. To address this problem, fuzzy PSI extends PSI by allowing the receiver, holding the set W , to learn those items q ∈ Q from the sender for which there exists some w ∈ W satisfying dist(q, w) ≤ δ under a specified distance metric. Recently, a substantial body of works [11], [12], [13], [14], [15], [16], [17], [18], [19], [20] have proposed a variety of fuzzy PSI constructions. Among these, van Baarsen and Pu [13] introduced the first generic fuzzy PSI protocols supporting arbitrary Lp∈[1,∞] distance. Although several follow-up works [17], [18] further improve performance, these protocols still incur super-linear complexity, e.g., exponential in the element dimension, which becomes prohibitively expensive in high-dimensional settings. More recently, Gao et al. [14] proposed the first fuzzy PSI protocols for Lp∈[1,∞] distance with linear complexity in the set size, the dimension, and the distance threshold. Dang et al. [16] further optimized this line of work by introducing the prefix representation [21] that reduces the dependence on the threshold to logarithmic, thereby reducing both computation and communication costs, particularly for large thresholds. Nevertheless, both schemes rely heavily on expensive additively homomorphic encryption operations, such as the ElGamal and Paillier schemes, which leads to poor concrete performance. Please refer to Table 1 and Section 1.2 for a more detailed discussion of related works. Motivated by the above, we raise the following question: Can we construct concretely efficient fuzzy PSI protocols for general Lp∈[1,∞] distance with linear complexity in the set size and the element dimension?
1.1. Our Contribution We answer the above question affirmatively and summarize our contributions as follows. 1) Shared-output OPPRF. We introduce a new building block, termed oblivious programmable PRF with secret-shared outputs (so-OPPRF), which enables oblivious evaluations of programmable PRF without revealing outputs to either party individually.
TABLE 1: Asymptotic complexities of existing fuzzy PSI protocols for Lp∈[1,∞] distance, where the sender holds m elements and the receiver holds n elements in a d-dimensional space, δ is the distance threshold. We ignore multiplicative factors of the computational security parameter κ and statistical security parameter λ. Metric
Protocol
Assumption
Communication
R, min > 2δ R, min > 4δ R, disj. proj. R, mini-univ. R ∧ S, min > 4δ R ∧ S, s-separate S, disj. hash S, disj. hash R ∧ S, disj. proj. R ∧ S, disj. proj. R ∧ S, disj. proj. R ∧ S, disj. proj. R, min > 2δ(d1/p + 1) R, min > δ/ρ R ∧ S, min > 2δ(d1/p + 1) R ∧ S, s-separate S, disj. hash R ∧ S, disj. proj. R ∧ S, disj. proj. R ∧ S, disj. proj. R ∧ S, disj. proj.
[13]
L∞
[20] [18] [15] [17] [19] [14] [16] Ours Ours-prefix [13]
Lp∈[1,∞)
[18] [15] [17] [14] [16] Ours Ours-prefix
Computation Sender
Receiver
O(δdn + 2d m) O(δ2d dn + m) O((δd)2 n + m) O((dn log δ + m(2 log δ)d )) O(d(m + 2d n) log δ) O(δ s ds (m + n)) O(d(δm + 2d n)) O(d log δ(n2d + m2d−s )) O(δd(m + n)) O (d(m + n) log δ) O (δd(m + n)) O (d(m + n) log δ)
O(2d dm) O(dm) O(d2 m) O(m(2 log δ)d ) O(d(m + 2d n) log δ) O(δ s ds m + n) O(δdm) O(2d−s dm log δ) O(δdm + n) O (d(m + n) log δ) O (δdm + dn) O (d(m + n) log δ)
O(δdn + 2d m) O(δ2d dn + m) O((δd)2 n + m) O((log δ)d n + dm log δ) O(2d n(d log δ + (log δ)d/2 )) O(δ s ds n + m) O(d2d n + m) O(2s dn log δ) O(δdn + m) O (d(m + n) log δ) O (δdn + dm) O (d(m + n) log δ)
O(δ2d dn + δ p m) O(δdn1+ρ + δ ρ mnρ log n) O(d(δm + 2d n) + p(m + 2d n) log δ) O(δ s ds (m + n) + pm log δ) O(d(δm + 2d n)) O(δd(m + n) + pm log δ) O (dpn log δ + dm log δ) O (δd(m + n) + pm log δ) O (dpn log δ + dpm log δ)
O((d + δ p )m) O((d + δ ρ )mnρ log n) O(d(δm + 2d n) + p(m + 2d n) log δ) O((δ s ds + p log δ)m + n) O(δdm) O(δdm + pm log δ + n) O (dpm log δ + dn log δ) O (δdm + dn + pm log δ) O (dpm log δ + dpn log δ)
O(δ2d dn + m) O(δdn1+ρ + mnρ log n) O(2d n(d + p log δ)) O(δ s ds n + pm log δ) O(d2d n + m) O(δdn + pm log δ) O (dpn log δ + dm log δ) O (δdn + dm + pm log δ) O (dpn log δ + dpm log δ)
– R/S denotes that the set of receiver/sender satisfies the assumption, and R ∧ S indicates that both sets satisfy the assumption. – disj. proj. is short for disjoint projection assumption, where each element has disjoint projections in some dimension with all other elements. – 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. – mini-univ is short for mini-universe assumption, where every ball can be mapped to a distinct vertex of the space. – s-separate means for every s dimensions, elements have disjoint projections in one of these s dimensions with all other elements where 1 ≤ s ≤ d. – 0 < ρ < 1/c is a parameter in locality-sensitive hashing where the distance between any receiver’s two elements is greater than cδ . – min > l means that the minimum distance between any two elements of the set is greater than l.
2) Modular fuzzy mapping. We present a modular protocol design of fuzzy mapping, which is a core component of fuzzy PSI, from shared-output OPPRF and shared-input OPRF. 3) Efficient fuzzy PSI. We propose efficient fuzzy PSI protocols for Lp∈[1,∞] distance metrics based on our fuzzy mapping, primarily leveraging lightweight symmetric-key operations, with linear complexity in the set size, the dimension, and the distance threshold. 4) Prefix optimizations. We incorporate prefix techniques to optimize the overhead of fuzzy PSI protocols for large distance thresholds, which reduces the computational and communication complexity to logarithmic in the distance threshold. 5) Extensive evaluations. We conduct extensive experiments under various parameter settings. Experimental results demonstrate that our protocols consistently and significantly outperform the state-of-the-art works across all settings, particularly, up to 80× faster computation and 19× lower communication.
1.2. Related Work Fuzzy PSI for Hamming distance. For a long time, research on fuzzy PSI primarily focused on the Hamming distance. Freedman et al. [2] first introduced the problem of secure fuzzy matching and proposed a protocol based on additively homomorphic encryption (AHE). Subsequent works [10], [21], [22], [23], [24], [25] improve the protocol’s complexity based on different techniques and assumptions.
Fuzzy PSI for Minkowski distance. More recently, a series of works have explored fuzzy PSI for Lp∈[1,∞] metrics. Garimella et al. [11] introduced the notion of structure-aware PSI, in which one party holds a structured dataset while the other holds an unstructured set of points. Their construction can be extended to fuzzy PSI for L∞ distance, but has a cost that scales with δ d . Chakraborti et al. [21] studied the problem for L1 distance and presented a useful technique known as prefix representation. Then, Garimella et al. [12] and Bui et al. [20] improved their previous work [11], reducing the complexity to (log δ)d with prefix representation. van Baarsen and Pu [13] proposed the first fuzzy PSI protocol for general L∞ and Lp distances based on the Decisional Diffie–Hellman (DDH) assumption. Their construct supposed each element has a minimum distance (2δ or 4δ ) from other elements. They subsequently improved their design using lightweight primitives [18], which significantly reduced the overall computational overhead. Similarly, they used prefix representation to achieve a complexity of (log δ)d . Several follow-up works further improved the performance but still incurred exponential complexity. Piske et al. [17] constructed the fuzzy PSI protocol based on a newly introduced primitive, distance-aware OT. They followed the disjoint hash assumption [19] where the whole input space is cut into grid cells and the spatial hashing scheme maps at most one element to every possible target grid cell. Their techniques rely on symmetric cryptographic primitives; however, their construction remains exponential
in the dimension d. Moreover, their protocol operates over a relatively small domain and supports only two-dimensional inputs for the L2 distance, which limits its practicality. Richardson et al. [19] generalized the approach of [26] and built a fuzzy PSI protocol using generic two-party computation, resulting in poor concrete efficiency. Chongchitmate et al. [27] proposed a protocol that achieves nearly linear complexity in the set size. Nevertheless, their design relies on garbled circuits and multiple PSI invocations, which significantly limits its practical efficiency. Building on [13], Gao et al. [14] proposed the first fuzzy PSI for Lp∈[1,∞] metrics, achieving linear complexity with respect to all parameters. They assumed that the set of both parties satisfies the disjoint projection assumption, where each element has disjoint projections in some dimension from all other elements. Later, Dang et al. [16] further improved this approach by adopting prefix representation to reduce the complexity to log δ . Nevertheless, both Gao et al. [14] and Dang et al. [16] heavily rely on the AHE, incurring considerable computational overhead. Recently, Zhang et al. [15] improved [14] by introducing a new framework for fuzzy PSI based on a stronger “s-separate” assumption. Although [15] solely uses symmetric cryptographic primitives, it suffers from a relatively high exponential factor δ s for both communication and computation overhead, especially for large δ . Other Solutions. A closely related line of works study private record linkage (PRL) [28], [29], [30], [31], [32], [33], [34], [35], whose goal is to identify common entities across disparate datasets while protecting the privacy of nonmatching records. Unlike our setting, these works typically do not rely on assumptions on the input distribution. Instead, many of them employ locality-preserving or localitysensitive hashing techniques [36], [37] to project multidimensional records into lower-dimensional representations, often at the expense of matching accuracy. Existing PRL protocols have been instantiated using a variety of privacy-enhancing techniques, including Bloom filters [38], differential privacy [39], and secure multiparty computation (MPC). Among them, only a small number of works [32], [33], [34], [35] provide cryptographic security without additional leakage. In particular, Khurram and Kerschbaum [32] proposed the first efficient cryptographically secure PRL protocol based on MPC. Their approach avoids the quadratic cost of all-pairs comparison by first securely sorting the records and then comparing only records that fall within the same comparison window. Nevertheless, the overall cost of their construction is dominated by the secure merge sorting procedure, resulting in an O(n log n) complexity, where n denotes the total number of records. Wei et al. [33] improved this line of works in both efficiency and empirical accuracy by incorporating locality-sensitive hashing [40]. However, their protocol leaks the number of comparisons, and its overall complexity remains O(n log n). To achieve stronger privacy guarantees, Stammler et al. [34] abandoned locality-based blocking and instead compare all record pairs, incurring a quadratic O(n2 ) complexity. Adir et al. [35] combined locality-sensitive hashing [37] with
PSI to obtain linear complexity. However, replacing generic MPC-based circuit for distance computation with standard PSI significantly reduces the computational overhead, but this simplification comes at the cost of reduced matching accuracy. While PRL protocols address the trade-off among security, efficiency, and accuracy in more general application settings, our goal is to design a protocol for structured sets satisfying certain assumptions, which allows us to avoid introducing false positives or negatives. Accordingly, we treat PRL as a closely related series of works, but center our subsequent discussion on prior fuzzy PSI protocols that realize the same functionality under certain assumptions. In this work, we focus on constructing concretely efficient fuzzy PSI protocols with linear complexity in both the set size and the dimension, while avoiding expensive public-key primitives such as AHE used in existing linearcomplexity constructions [14], [16]. Table 1 compares the asymptotic complexities of our protocols with prior works for Lp∈[1,∞] distance. Among prior works under the same assumptions, we report only the protocols with the best asymptotic complexity.
2. Technical overview We begin by introducing the necessary notations. The sender S holds a set Q = {qj }j∈[m] of size m, and the receiver R holds a set W = {wi }i∈[n] of size n, both defined over a d-dimensional space. We use qj,k to denote the k -th coordinate of qj . For any qj ∈ Q and wi ∈ W , we say that qj and wi are δ -close if dist(qj , wi ) ≤ δ , where δ denotes the distance threshold.
2.1. Fuzzy PSI Paradigm from Fuzzy Mapping Recent works [13], [14], [16], [17] show that fuzzy PSI protocols typically consist of two phases: coarse mapping and refined filtering. (1) In the coarse mapping phase, each element in both parties’ sets is mapped to an identifier (ID). Any two elements that are within distance δ , one from the sender and one from the receiver, are guaranteed to receive the same ID. This phase may introduce false positives, but no false negatives. (2) In the refined filtering phase, for each candidate pair with the same ID, the parties further perform an exact distance check to eliminate the false positives generated during the coarse mapping phase. The above idea is similar to hashing-based standard PSI protocols and reduces the number of necessary distance comparisons from O(mn) to O(n) or O(m). To realize the coarse mapping phase, Gao et al. [14] propose a generalized protocol, termed fuzzy mapping, which takes sets Q and W as input and outputs identifier sets IDQ and IDW for the sender and receiver, respectively. The protocol guarantees that for any two elements qj ∈ Q and wi ∈ W satisfying dist(qj , wi ) ≤ δ , it holds that IDqj = IDwi . Subsequently, the refined filtering phase is carried out via fuzzy matching, which takes as input every
R {xi }i∈[n]
{xi }i∈[n]
S {(qj , zj )}j∈[m]
Fso-OPRF
{fiR }i∈[n]
k, {fiS }i∈[n]
D := OKVS.Encode {(qj , zj − Fk (qj ))}j∈[m]
di = OKVS.Decode(D, xi )
Output {fiR + di }i∈[n]
Output {fiS }i∈[n]
Figure 1: Construction of so-OPPRF from so-OPRF.
and the obliviousness means that if the OKVS encodes random values, the encoding D is independent of the encoded keys. To this end, the sender computes an OKVS encoding D on {(qj , zj − PRF(k, qj ))}j∈[m] and sends D to the receiver. Finally, the sender outputs yiS := fiS , while the receiver outputs yiR := fiR + OKVS.Decode(D, xi ). For each programmed point xi = qj , correctness holds immediately since yiS +yiR = fiS +fiR +zj −PRF(k, qj ) = zj . The pseudorandomness of unprogrammed points follows from the functionality of so-OPRF. The above steps are illustrated in Figure 1. In the following Sections 2.3 and 2.4, we will show how to design fuzzy PSI from so-OPPRF.
2.3. Fuzzy Mapping from so-OPPRF and si-OPRF pair (qj , wi ) sharing the same ID and returns qj to the receiver if and only if dist(qj , wi ) ≤ δ . In this work, we follow this fuzzy PSI paradigm, but introduce new techniques to realize the fuzzy mapping and fuzzy matching phases with linear complexity in the set size and dimension, primarily using lightweight symmetric-key operations1 .
2.2. OPPRF with Shared Outputs An oblivious pseudorandom function (OPRF) allows a receiver to input a value x and obtain PRF(k, x), where the PRF key k is privately held by the sender. Programmable OPRF (OPPRF), introduced by Kolesnikov et al. [43], extends this functionality by allowing the sender to program the PRF on designated points: for each sender’s chosen pair (yi , zi ), the functionality enforces PRF(k, yi ) = zi , while all non-programmed inputs receive pseudorandom outputs. In this work, we introduce a variant of OPPRF, termed shared-output OPPRF (so-OPPRF), which serves as a core building block in our fuzzy mapping and fuzzy PSI protocols. A so-OPPRF is identical to a standard OPPRF except that it outputs secret shares of PRF(k, x) to the two parties rather than revealing the PRF value to the receiver. We construct an efficient so-OPPRF protocol by combining an oblivious key-value store (OKVS) [44] with a sharedoutput OPRF (so-OPRF) [45], [46], following the classical OPPRF paradigm [47], [48]. Concretely, the parties first run a so-OPRF, in which the sender inputs a PRF key k and the receiver inputs a set X , and they obtain secret shares fiS , fiR of PRF(k, xi ) for each xi ∈ X . To program the PRF on the chosen points {(qj , zj )}j∈[m] , the sender uses OKVS to encode these points. OKVS [44] consists of two algorithms: Encode takes as input a set of key-value pairs {(kj , vj )}j∈[m] and outputs an encoding D while Decode takes as input a key k and D, and outputs a value v . The correctness ensures that OKVS.Decode(D, kj ) outputs vj , 1
Our protocols invoke OT and VOLE, instantiated via pseudorandom correlation generators (PCGs) [41], [42]. In PCGs, the seed setup phase requires a small number of base OTs implemented with public-key operations, while the seed expansion phase relies on linear codes. Both phases are highly efficient in practice [17], [18].
We present a modular framework of fuzzy mapping with the following two steps. (1) Local mapping: the sender constructs a private local mapping HQ that maps the set Q’s elements to unique local IDs, while guaranteeing that for each wi ∈ W , if there exists qj such that dist(qj , wi ) ≤ δ , HQ (wi ) = HQ (qj ) holds. Similarly, the receiver generates a private local mapping HW . (2) Global mapping: two parties interactively compute the global IDs as IDqj := PRFk (HQ (qj ) + HW (qj )) and IDwi := PRFk (HQ (wi ) + HW (wi )) without revealing any information about Q, W . Along with the correctness of local mapping, it ensures that if dist(qj , wi ) ≤ δ , it holds IDqj = IDwi . It is worth noting that compared to the existing fuzzy mapping [14], [16], our main contribution lies in the modular PRF-based global mapping design, which simplifies protocol comprehension and facilitates efficient protocol instantiation. We elaborate on these aspects and the underlying technical methods in the remainder of this section. To instantiate the above framework, we present an efficient fuzzy mapping protocol for L∞ distance. The following description focuses on the receiver’s protocol due to the symmetric design. Specifically, in the first local mapping step, same as the prior works [14], [15], [16], for each qj,k , the sender locally assigns a random value rj,k to the interval [qj,k − δ, qj,k + δ] centered on qj,k , formally represented as a set of the key-value pairs L := {(k∥(qj,k +t), rj,k )}j∈[m],k∈[d],t∈[−δ,δ] . We will explain how to handle overlaps later. The sender then P defines the local mapping HQ such that HQ (qj + ξ) := k∈[d] rj,k for each qj ∈ Q and ξ ∈ [−δ, δ]d . Then, in the global mapping step, to obtain HQ (wi ) without revealing any information to each other, the receiver obliviously retrieves values rwi ,k from the sender’s key-value list L with the inputs k∥wi,k for each dimension k . It needs to ensure that for each k ∈ [d], if |wi,k − qj,k P| ≤ δ , then rwi ,k = rj,k holds and hence HQ (wi ) = k∈[d] rwi ,k = HQ (qj ); otherwise, rwi ,k is a random value. We observe that the above functionality can be realized by invoking the OPPRF protocol, where the sender inputs the programmed points L, and the receiver inputs queries k∥wi,k and learns either the designated rj,k or
R {wi }i∈[n]
S {qj }j∈[m]
{qj }j∈[m]
Local Mapping {HQ (qj )}j∈[m]
{wi }i∈[n]
Global Mapping Fso-OPPRF
R {HQ (wi )}i∈[n]
i ∈ [n] R {HQ (wi )+HW (wi )}
HQ (·) S {HQ (wi )}i∈[n]
Randomize Fsi-OPRF
S {HQ (wi )}i∈[n]
{IDwi }i∈[n]
Output {IDwi }i∈[n]
Figure 2: Construction of fuzzy mapping from so-OPPRF and si-OPRF. The sender and receiver can switch roles and repeat the process symmetrically. pseudorandom values. However, this will leak to the receiver additional information about partial matches on individual dimensions. That is, since the sender programs all points in the interval [qj,k − δ, qj,k + δ] to the same rj,k , the receiver learns the same OPPRF evaluation on two different wi,k , wi′ ,k ∈ [qj,k − δ, qj,k + δ], leaking the range of some qj,k . Existing solutions [14], [16] employ AHE to avoid this leakage, but result in prohibitively large overhead. Applying so-OPPRF. We adopt our so-OPPRF protocol to prevent the information leakage to the receiver while achieving better efficiency than AHE-based solutions. Specifically, with the same inputs L and {k∥wi,k }k∈[d] as above, soS OPPRF returns the secret shares {rw } to the sender i ,k k∈[d] R and {rw } to the receiver. Then, the sender sets k∈[d] i ,k P S S R H (w ) := k∈[d] rwi ,k and the receiver sets HQ (wi ) := PQ i R r , both of which are the secret shares of H Q (wi ). k∈[d] wi ,k However, HQ (wi ) can not be directly revealed to the receiver. The reason is that in the local mapping [14], when there are overlapped intervals, later random values will overwrite earlier values. This enlarges the valid radius-δ interval of qj,k , thereby introducing false positives. This may result in two elements wi1 , wi2 satisfying HQ (wi1 ) = HQ (wi2 ) even if dist(wi1 , wi2 ) > δ , which leaks the sender’s information, i.e., there is a sender’s element nearby wi1 , wi2 . Existing protocols [14], [16] employ a symmetric execution2 to additionally compute HW (wi ) and derive IDwi from HQ (wi ) + HW (wi ) with a customized combination of expensive AHE and Diffie–Hellman key-exchange. Applying si-OPRF. To address this leakage, we introduce a 2
The method [16] lacks this symmetric execution and causes the above privacy leakage issue, which has been confirmed by the authors via our private communication. Table 1 gives the corrected complexity with the symmetric execution.
R {wi }i∈[n]
S {qj }j∈[m]
Execute symmetrically {wi }i∈[n]
{qj }j∈[m]
Fuzzy Mapping {IDqj }j∈[m]
{IDwi }i∈[n] i ∈ [n],k ∈ [d],t ∈ [-δ,δ]
j ∈ [m],k ∈ [d]
{(IDwi ∥k∥wi,k +t, 0)}
{IDqj ∥k∥qj,k }
Fso-OPPRF
R {rj,k }j∈[m],k∈[d] P R rjR = k∈[d] rj,k
{rjR }j∈[m]
S {rj,k }j∈[m],k∈[d] P S rjS = k∈[d] rj,k
{rjS }j∈[m]
FPEQT
{bj }j∈[m] {bj }j∈[m]
FOT
{(⊥, qj )}j∈[m]
{zj }j∈[m]
Output {zj | bj = 1}j∈[m]
Figure 3: Construction of fuzzy PSI from so-OPPRF. new building block, called OPRF with secret-shared inputs (si-OPRF), and realize it with MPC-friendly PRF [46]. Different from so-OPRF, in si-OPRF, the PRF key k and the PRF input x are secret shared between two parties. After evaluation, it returns the plain PRF output PRFk (x) to the receiver. To obtain the final IDs IDwi , the sender and the S R receiver input secret shares HQ (wi ) and HQ (wi )+HW (wi ) and secret shared k into si-OPRF. Then the receiver learns IDwi := PRFk (HQ (wi ) + HW (wi )). This ensures that even for HQ (wi1 ) = HQ (wi2 ), if local mapping ensures that HW (wi1 ) ̸= HW (wi2 ), the receiver learns different IDwi1 and IDwi2 . Similarly, the sender learns IDqj := PRFk (HQ (qj ) + HW (qj )), where the same secret-shared PRF key k is used by both parties in two si-OPRF invocations. This ensures that IDqj = IDwi for dist(qj , wi ) ≤ δ due to HQ (qj ) = HQ (wi ) and HW (qj ) = HW (wi ). The above processes are illustrated in Figure 2.
2.4. Fuzzy PSI from so-OPPRF The fuzzy mapping protocol above guarantees that all δ -close elements between the sender and the receiver are assigned the same IDs, but it may introduce false positives. We further utilize our so-OPPRF protocol to perform a refined filtering that excludes elements that are not truly δ -close, thereby achieving fuzzy PSI for both the L∞ and Lp distances with p ∈ [1, ∞). We here focus on the protocol for L∞ distance. As shown in Figure 3, two parties first invoke fuzzy mapping procedure to get the IDs, and then execute the so-OPPRF protocol, where the receiver inputs {(IDwi ∥k∥(wi,k + t), 0)}t∈[−δ,δ],i∈[n],k∈[d] and the
sender inputs {IDqj ∥k∥qj,k }j∈[m],k∈[d] . The sender receives S R {rj,k }j∈[m],k∈[d] and the receiver receives {rj,k }j∈[m],k∈[d] . That means if IDqj = IDwi and the distance between qj,k and wi,k is within δ , both parties will obtain the secret shares of 0 in dimension k ; otherwise, they hold random P values. S Then, for j ∈ [m], the sender computes rjS := k∈[d] rj,k , P R R and the receiver computes rj := k∈[d] rj,k . For each δ close element pair with the same ID, so-OPPRF guarantees that rjS and rjR are secret shares of the designated value 0. In contrast, if IDqj is different from all IDs of W or there exists wi with the same ID but the distance |wi,k − qj,k | > δ for some dimension k , then rjS and rjR will be secret shares of a random value according to the randomness property of soOPPRF. After that, similar to prior works, both parties can employ a cheap Private Equality Test (PEQT) protocol to verify whether they hold secret shares of 0. Finally, the two parties invoke an Oblivious Transfer (OT) protocol, where the receiver selects the sender’s elements based on outcomes of the PEQT protocol.
2.5. Fuzzy PSI with prefix optimizations We further optimize our fuzzy PSI protocols using prefix techniques [12], [16], [18], [20] for large distance threshold δ . This modification reduces the communication and computation complexity from O (δ) to O (log δ). The high-level idea to incorporate prefix techniques in our framework is that the sender in the so-OPPRF protocol does not need to program the entire interval [qj,k − δ, qj,k + δ] of size 2δ + 1, but only O (log δ) prefixes that together cover the interval. We present customized protocols to instantiate this optimization. In contrast to the state-of-the-art protocol [16] that employs expensive AHE, our protocols still use our soOPPRF and the newly introduced equality-conditional selection protocol, which significantly improve overall efficiency. Please refer to Section 7 for more details.
3. Preliminary 3.1. Notation We use κ and λ to denote the computational and statistical security parameters, respectively. Let negl(x) be a negligible function in x if it vanishes faster than the inverse of any polynomial in x. We use [a, b] to denote the set {a, . . . , b} and [a] to denote the set {1, . . . , a}. For a set S , |S| denotes the cardinality of S . By r ← S , we denote that r is sampled from the set S uniformly at random. We use 1{event} to denote an indicator function, which equals 1 if the event occurs and 0 otherwise. All protocols in this work are secure in the semi-honest model and the definition is deferred to Appendix A.1.
fuzzy PSI works [14], [16], we utilize the disjoint projection assumption for the sets of both sender and receiver. That is, each element maintains a distance of more than 2δ on at least one dimension from the set’s other elements. We define it formally as follows: Definition 1 (Disjoint projection). A set W ∈ Un×d satisfies the δ -disjoint projection assumption, if for any wi ∈ W , there exists k ∈ [d] such that for any wj ∈ W for j ̸= i it holds [wi,k − δ, wi,k + δ] ∩ [wj,k − δ, wj,k + δ] = ∅. As shown in the work [13], if the set’s elements are uniformly distributed, the set satisfies the disjoint projection assumption defined in Definition 1 with probability 1 − negl(d). Functionality FFPSI Parameters: Sender S and receiver R with input sizes m, n, respectively. Distance metric dist(·, ·) and threshold δ . Protocol: 1) Wait for input Q = {qj }j∈[m] ∈ Ud×m from S and W = {wi }i∈[n] ∈ Ud×n from R. 2) Output Z := {qj |∃i ∈ [n], dist(qj , wi ) ≤ δ} to R.
Figure 4: Functionality of fuzzy PSI.
3.3. Oblivious Key-Value Store An oblivious key-value store (OKVS) [44] is a data structure consisting of two algorithms: Encode takes as input a set of key-value pairs and outputs a data structure, and Decode takes as input a key and the data structure and outputs a value. The obliviousness implies that if the OKVS encodes random values, the data structure is independent of the encoded key set. Definition 2 (Oblivious Key-Value Store [44]). An oblivious key-value store (OKVS) is parameterized by a key space K, a value space V , and the statistical security parameter λ, and consists of two algorithms: n • Encode: on input a set of key-value pairs L ∈ (K×V) , outputs a vector D ∈ V m or a failure indicator ⊥ with probability bounded by 1/2λ . m • Decode: on input a vector D ∈ V and a key k ∈ K, outputs a value v ∈ V . Correctness: For all L ∈ (K × V)n with distinct keys for which D ← Encode(L) and D ̸= ⊥, it holds that ∀(k, v) ∈ L, Decode(D, k) = v . Obliviousness: For any distinct {k1 , . . . , kn } ∈ Kn and {k1′ , . . . , kn′ } ∈ Kn , Encode does not output ⊥ on {k1 , . . . , kn } and {k1′ , . . . , kn′ }, and then the following distributions are statistically indistinguishable
3.2. Functionality of Fuzzy PSI
{Encode({(k1 , v1 ), . . . , (kn , vn )}) | vi ← V, i ∈ [n]} ≈s {Encode({(k1′ , v1 ), . . . , (kn′ , vn )}) | vi ← V, i ∈ [n]}.
We formally define the ideal functionality for fuzzy PSI in Figure 4. Same as the state-of-the-art linear-complexity
Double obliviousness: For any distinct {k1 , . . . , kn } ∈ Kn such that Encode does not output ⊥ on {k1 , . . . , kn }, then
Functionality Fso-OPRF Parameters: Sender S and receiver R. PRF F : K × U → F. Protocol: 1) Wait for input X = {x1 , . . . , xn } ⊆ U from R. 2) Wait for input k ∈ K from S . 3) For i ∈ [n], compute yi := Fk (xi ) and sample yiS , yiR ← F such that yiS + yiR = yi ∈ F. 4) Output {yiS }i∈[n] to S and {yiR }i∈[n] to R.
Figure 5: Functionality of oblivious PRF with secret-shared outputs. Functionality Fsi-OPRF Parameters: Sender S and receiver R. PRF F : K × U → F. Protocol: S 1) Wait for input X S = {xS 1 , . . . , xn } ⊆ U from S and R X R = {xR , . . . , x } ⊆ U from R such that xi := 1 n R xS i + xi ∈ F. 2) Wait for input kS ∈ K from S and kR ∈ K from R such that k := kS + kR ∈ K. 3) For i ∈ [n], compute yi := Fk (xi ). 4) Output {yi }i∈[n] to R.
Figure 6: Functionality of oblivious PRF with secret-shared inputs. {Encode({(k1 , v1 ), . . . , (kn , vn )}) | vi ← V, i ∈ [n]} is statistically indistinguishable from uniform distribution over V m. Independence: For any L := {(ki , vi )i∈[n] } ∈ (K × V)n with distinct keys such that D ← Encode(L) and D ̸= ⊥, it holds that for any k ∈ / {ki }i∈[n] , Decode(D, k) is statistically indistinguishable from uniform distribution over V.
3.4. Secret shared OPRF We introduce two functionalities of OPRF with secret shared output (so-OPRF) and OPRF with secret shared key and input (si-OPRF) in Figure 5 and Figure 6, respectively. We instantiate the above two variants of OPRF using MPC-friendly alternating-moduli (weak) PRF, which was first proposed by Boneh et al. [49] and later optimized in [46], [50], [51]. At a high level, this construction takes as input a key k and a value x, and multiplies them by various matrices modulo two different primes, e.g., 2 and 3. More concretely, the PRF construction in [46] is defined as F (k, x) := B ·2 (A ·3 [k ◦2 (G ·2 [x||1])]), where n×(d+1) , A ∈ Fm×n , B ∈ Ft×m are uniformly G ∈ F2 3 2 distributed, and ·p , ◦p are multiplication and componentwise multiplication modulo p. In particular, we make use of the parameterization d = κ, n = 4κ, m = 2κ, t = κ which implies G is an expanding matrix and B is a compressing matrix. The security of this construction relies on the assumption [49] that linear operations over two different moduli result in a highly non-linear and unpredictable function when viewed over F2 or F3 .
3.5. Functionalities of Building Blocks We present the functionalities of the private equality/interval test in Figure 7. Chakraborti et al. [21] introduced an efficient private interval test protocol based on prefix representation. Both the communication and computation complexities are O (log δ). Besides, we introduce the functionalities FMUX and FssPEQT , which are deferred to Appendix B.1. Functionality FInterval Parameters: Sender S and receiver R. Threshold δ . Protocol: 1) Wait for input xS from S and xR from R. 2) Output 1 to R if xS + xR ≤ δ , otherwise output 0.
Figure 7: Functionality of private interval test.
3.6. Prefix Representation Prefix representation, first proposed by Chakraborti et al. [21] and further studied and formalized in [12], [16], [18], [20], is used to improve the efficiency of fuzzy PSI. Let x = xℓ xℓ−1 · · · x1 ∈ {0, 1}ℓ be a binary string. We first introduce the following notations: • Prefix(xℓ xℓ−1 · · · x1 , k) = xℓ xℓ−1 · · · xk+1 • AllPrefix(xℓ xℓ−1 · · · x1 , k) = {xℓ xℓ−1 · · · xj+1 }j∈[0,k] • UpBound(xℓ xℓ−1 · · · xk ) = xℓ xℓ−1 · · · xk ∥11 · · · 1 • LowBound(xℓ xℓ−1 · · · xk ) = xℓ xℓ−1 · · · xk ∥00 · · · 0 ∗ • Interval(xℓ xℓ−1 · · · xk ) = {xℓ · · · xk ∥x }x∗ ∈{0,1}k−1 Previous works [16], [18] gave the definition of Decompose as following: Definition 3. Given an integer interval [a−δ, a+δ], there is an algorithm Decompose to succinctly encode the interval into a list of prefixes S {pi }i∈[µ̂] such that: • [a − δ, a + δ] = i∈[µ̂] Interval(pi ) • For any i ∈ [µ̂], if a binary string p is a prefix of pi , Interval(pi ) ⊈ [a − δ, a + δ] The algorithm Decompose [16], [18] has a computation complexity O (log δ) and the number of prefixes µ̂ is also O (log δ). The length of prefixes pi is at least ℓ−µ′ where µ′ is the number of wildcards (i.e., non-determined bit strings) and µ′ = O (log δ). Precisely, if δ is a power of 2, the number of prefixes µ̂ has a lower bound of ⌈log(2δ + 1)⌉ and µ′ has an upper bound of ⌊log(2δ + 1)⌋ [18]. In this paper, we set our threshold δ to a power of 2 for simplicity. Unless otherwise specified, we denote µ̂ = 2 + log δ and µ′ = 1 + log δ or log δ . For a binary string x ∈ {0, 1}ℓ , there are µ′ + 1 prefixes of length at least ℓ − µ′ and we denote µ = µ′ + 1.
4. OPPRF with Shared Outputs We introduce a new variant of OPPRF, termed soOPPRF, whose outputs are secret-shared between two parties. So-OPPRF is useful in scenarios where outputs cannot
Functionality Fso-OPPRF Parameters: Sender S and receiver R with input sizes m, n, respectively. Protocol: 1) Wait for input L = {(qj , zj )}j∈[m] ⊆ U × F from S and X = {xi }i∈[n] ⊆ U from R. 2) Sample a random function F ′ : U → F such that F ′ (q) = z for (q, z) ∈ L. 3) For i ∈ [n], compute yi := F ′ (xi ) and sample yiS , yiR ← F such that yiS + yiR = yi ∈ F. ′ 4) Output {yiS }i∈[n] and OF to S and {yiR }i∈[n] to R.
Figure 8: Functionality of oblivious programmable PRF with secret-shared outputs. Protocol Πso-OPPRF Parameters: Sender S and receiver R with input sizes m, n, respectively. PRF F : K × U → F. Input: S inputs L = {(qj , zj )}j∈[m] ⊆ U × F. R inputs X = {xi }i∈[n] ⊆ U. Protocol: 1) S samples k ← K. S and R invoke functionality Fso-OPRF , where S inputs k and R inputs X = {xi }i∈[n] . S receives {fiS }i∈[n] , and R receives {fiR }i∈[n] , where fi := Fk (xi ) ∈ F. 2) S computes PRF values Fk (qj ) for j ∈ [m] and computes the OKVS encoding D := OKVS.Encode(L′ ), where L′ := {(qj , zj − Fk (qj ))}j∈[m] . 3) S sends D to R and R computes di := OKVS.Decode(D, xi ) for i ∈ [n]. 4) S defines the function F ′ (q) := Fk (q) + OKVS.Decode(D, q). ′ 5) S outputs {yiS := fiS }i∈[n] and OF , and R outputs R R {yi := fi + di }i∈[n] .
Figure 9: Protocol of oblivious programmable PRF with secret-shared outputs.
be revealed to either party individually, which may be of independent interest. As we have presented our idea in Section 2.2, here we illustrate the ideal functionality in Figure 8 and the detailed protocol in Figure 9. We show the protocol’s security in Theorem 1, and the security proof is deferred to Appendix A.2. Theorem 1. The protocol Πso-OPPRF in Figure 9 realizes the functionality Fso-OPPRF in Figure 8 against semi-honest adversaries in the (Fso-OPRF )-hybrid model if OKVS satisfies the correctness, double obliviousness, and independence properties defined in Definition 2.
5. Efficient Fuzzy Mapping Fuzzy mapping (FMap), introduced by Gao et al. [14], enables two parties to assign identifiers to their respective set elements. If an element from the sender S and an element from the receiver R are sufficiently close, they
Procedure LocalMap Parameters: Distance threshold is δ . Prefix parameter µ̂ = 2 + log δ . Input: A set Q = {qj }j∈[m] ∈ Ud×m . Protocol: 1) Initialize List := ∅ and intervalk := ∅ for k ∈ [d]. 2) For each j ∈ [m] and each k ∈ [d]: • Sample rj,k and define Uj,k := [qj,k − δ, qj,k + δ]. • For each (U, r) ∈ intervalk if Uj,k ∩ U ̸= ∅, remove (U, r) from intervalk and update Uj,k = Uj,k ∪ U . • Set intervalk := intervalk ∪ {(Uj,k , rj,k )}. Pd 3) For each j ∈ [m], set pidqj := k=1 rk , where rk satisfies that qj,k ∈ Uk and (Uk , rk ) ∈ intervalk . 4) For each k ∈ [d] and each (U, r) ∈ intervalk : • Without prefix optimization: For each x ∈ U , set List := List ∪ {(k∥x, r)}. • With prefix optimization: Partition interval U into consecutive, disjoint sub-intervals {Uj }j∈[ϵ] , such that |Uj | = 2δ + 1 for j ∈ [ϵ − 1] and |Uϵ | ≤ 2δ + 1. For each j ∈ [ϵ], compute {xj,h }h∈[µ̂] := Decompose(Uj ) and set List := List ∪ {(k∥xj,h , 0∥r)}h∈[µ̂] . 5) Pad List with dummy items so that its size equals • Without prefix optimization: md(2δ + 1). • With prefix optimization: md(log δ + 2). 6) Output {pidqj }j∈[m] and List.
Figure 10: Procedure of local mapping and its variant with prefix optimization. will be mapped to the same identifier. We recall the formal definition from Gao et al. [14] as follows. Definition 4 (Fuzzy mapping [14]). A two-party protocol ΠFMap , where S inputs Q = {qj }j∈[m] ∈ Ud×m and learns {IDqj }j∈[m] ∈ Fm and R inputs W = {wi }i∈[n] ∈ Ud×n and learns {IDwi }i∈[n] ∈ Fn , is a secure fuzzy mapping protocol for distance metric dist and threshold δ against semi-honest adversaries, if and only if it satisfies: 1) Correctness: For any w ∈ W and q ∈ Q, if dist(w, q) ≤ δ , then IDq = IDw . 2) Distinctiveness: For any wi , wi′ ∈ W and i ̸= i′ , Pr[IDwi = IDwi′ ] ≤ negl(λ). 3) Security: Considering a corrupted sender S , for any Q ∈ Ud×m and any W, W ′ ∈ Ud×n , it holds that Π ′ viewΠ S (Q, W ) ≈c viewS (Q, W ). Similarly, considering a corrupted receiver R, for any W ∈ Ud×n and any Q, Q′ ∈ Ud×m , it holds that viewΠ R (Q, W ) ≈c ′ viewΠ (Q , W ) . R As we have presented our idea in Section 2.3, here we give the construction of the fuzzy mapping protocol for L∞ distance in Figure 11 and its sub-procedure local mapping in Figure 10. We note that for any w, q , the fact that dist∞ (q, w) ≤ distp (q, w) holds. Therefore, we will use fuzzy mapping for L∞ distance in fuzzy PSI protocols for both L∞ and Lp distance, since fuzzy mapping can tolerate false positives.
Protocol ΠFMap Input: S inputs Q = {qj }j∈[m] ∈ Ud×m and R inputs W = {wi }i∈[n] ∈ Ud×n . Protocol: 1) S runs LocalMap(Q) and obtains ({pidqj }j∈[m] , ListS ). R runs LocalMap(W ) and obtains ({pidwi }i∈[n] , ListR ). 2) S and R sample secret shares kS , kR of the PRF key, respectively. 3) S and R invoke functionality Fso-OPPRF , where S as the sender inputs ListS and R as the receiver inputs S {k∥wi,k }i∈[n],k∈[d] . S receives {rw } and i ,k i∈[n],k∈[d] R R receives {rwi ,k }i∈[n],k∈[d] . P S S 4) For i ∈ [n], S computes rw := k∈[d] rw , and R i i ,k P R R computes rwi := k∈[d] rwi ,k . 5) S and R invoke Fsi-OPRF , where S as the sender inS puts (kS , {rw } ), and R as the receiver inputs i i∈[n] R R (k , {rwi + pidwi }i∈[n] ) and learns {IDwi }i∈[n] . 6) Symmetrically, S and R invoke functionality Fso-OPPRF , where R as the sender inputs ListR and S as the receiver inputs {k∥qj,k }j∈[m],k∈[d] . S receives {rqSj ,k }j∈[m],k∈[d] and R receives {rqRj ,k }j∈[m],k∈[d] . P 7) For j ∈ [m], S computes rqSj := k∈[d] rqSj ,k , and R P computes rqRj := k∈[d] rqRj ,k . 8) S and R invoke Fsi-OPRF , where R as the sender inputs (kR , {rqRj }j∈[m] ), and S as the receiver inputs (kS , {rqSj +pidqj }j∈[m] ) and learns {IDqj }j∈[m] ∈ F2ℓ .
∞ Protocol ΠL FPSI Parameters: Distance threshold δ . Input: S inputs Q = {qj }j∈[m] ∈ Ud×m and R inputs W = {wi }i∈[n] ∈ Ud×n . Protocol: 1) S and R invoke sub-protocol ΠFMap , where S inputs Q and R inputs W . S obtains {IDqj }j∈[m] and R obtains {IDwi }i∈[n] . 2) S and R invoke functionality Fso-OPPRF , where R as the sender inputs {(IDwi ∥k∥(wi,k + t), 0)}t∈[−δ,δ],i∈[n],k∈[d] and S as the receiver inputs {IDqj ∥k∥qj,k }j∈[m],k∈[d] . S receives S R {rj,k }j∈[m],k∈[d] and R receives {rP j,k }j∈[m],k∈[d] . S S 3) For j ∈ [m], S computes rj := k∈[d] rj,k , and R P R R computes rj := k∈[d] rj,k . 4) S and R invoke functionality FPEQT , where S inputs {rjS }j∈[m] and R inputs {−rjR }j∈[m] . R receives {bj }j∈[m] , where bj := 1{rjS + rjR = 0}. 5) S and R invoke functionality FOT , where S inputs {(⊥, qj )}j∈[m] , and R inputs {bj }j∈[m] and receives {zj }j∈[m] . 6) R outputs Z := {zj | bj = 1 for j ∈ [m]}.
Figure 12: Protocol of fuzzy PSI for L∞ distance.
Theorem 2. The ΠFMap protocol in Figure 11 satisfies the correctness, distinctiveness, and security properties defined in Definition 4 for L∞ distance, if both parties’ sets satisfy the disjoint projection assumption.
dependent of any other assignments. Then, we have that IDwi := PRF(k, ListR [ki ∥wi,ki ] + . . .). According to the functionality of si-OPRF, IDwi is computationally indistinguishable from a uniformly random value. Therefore, a union bound shows that the probability of that there exists i, i′ ∈ [n] such that i ̸= i′ and IDwi = IDwi′ ∈ F is at most n2 /|F|. With |F| ≥ n2 · 2λ , the probability n2 /|F| ≤ 1/2λ is negligible. Security. Since the protocol is symmetric, we only consider the corrupted sender S . Let IDQ (W ) denote the S ’s output from the real-world protocol where S inputs Q and R inputs W . We show the simulator SimFMap (Q, IDQ (W )): S
Proof. Correctness. For any wi ∈ W and qj ∈ Q, if dist(wi , qj ) ≤ δ , then for any k ∈ [d], |wi,k − qj,k | ≤ δ always holds. Therefore, all these wi,k are assigned S R in ListS and rw + rw = ListS [k∥wi,k ] according i,k i,k to the functionality Fso-OPPRF . Moreover, the LocalMap procedure ensures that the 2δ + 1 points on dimension k at qj,k all have the same assignment, hence P centered S R ) = pidqj holds. Similarly, it holds that (rw + rw k∈[d] i,k i,k P S R wi . The identifiers are computed k∈[d] (rqj,k + rqj,k ) = pid P as follows IDqj := PRFk ( k∈[d] (rqSj,k + rqRj,k ) + pidqj ) and P S R IDwi := PRFk ( k∈[d] (rw + rw ) + pidwi ). Since the i,k i,k PRF key is the same for both PRF evaluations on qj and wi , then IDqj = IDwi when dist(wi , qj ) ≤ δ . Distinctiveness. Since the R’s set W satisfies the disjoint projection assumption, without loss of generality, for each wi , assume the interval of [wi,ki − δ, wi,ki + δ] on dimension ki is disjoint from the length-(2δ + 1) intervals of other elements of W . Thus, the assignment ListR [ki ∥wi,ki ] is a uniformly random value and is in-
runs LocalMap(Q) and records the sampled 1) SimFMap S randomness. 2) SimFMap randomly samples the PRF key share k S . S FMap S 3) SimS randomly samples {rw } . i ,k i∈[n],k∈[d] FMap S 4) SimS randomly samples {rqj ,k }j∈[m],k∈[d] . 5) SimFMap appends the above values and (Q, IDQ (W )) S into the simulated view. We show that the output by SimFMap is indistinS guishable from the real protocol. The only difference is S {rw } and {rqSj ,k }j∈[m],k∈[d] . They are random i ,k i∈[n],k∈[d] secret shares in the real protocol according to the so-OPPRF functionality, while they are randomly sampled in the simulated view with the same distribution. Therefore, for any FMap Q, W , it holds that viewΠ (Q, IDQ (W )). S (Q, W ) ≈c SimS Moreover, since the S ’s set Q satisfies the disjoint projection assumption, as shown in the above analysis of distinctiveness, IDQ is computationally indistinguishable from uniformly random values for any W . Then, for any Q, W , it holds that SimFMap (Q, IDQ (W )) ≈c SimFMap (Q, R ← Fm ). S S
Figure 11: Protocol of fuzzy mapping for L∞ distance. We show that the above protocol satisfies the fuzzy mapping definition in Theorem 2.
FMap Therefore, we have viewΠ (Q, R ← S (Q, W ) ≈c SimS Π m ′ F ) ≈c viewS (Q, W ). This completes the proof.
6. Fuzzy PSI 6.1. Fuzzy PSI for L∞ Distance We have presented our idea in Section 2.4 and the detailed fuzzy PSI protocol for L∞ distance is illustrated in Figure 12. We show the protocol’s correctness as follows. Proof. Correctness. For each qj ∈ Q, if there exists wi ∈ W such that dist(qj , wi ) ≤ δ , the correctness of the fuzzy mapping in Theorem 2 guarantees that IDqj = IDwi . Consequently, by the correctness of the functionalities Fso-OPPRF , FPEQT , and FOT , the receiver correctly obtains bj = 1 and the corresponding element qj . On the other hand, for each qj ∈ Q, if dist(qj , wi ) > δ for all wi ∈ W , two cases arise due to the false positives introduced by the fuzzy mapping. (1) The first case is IDqj ̸= IDwi for any wi ∈ W . According to the correctness of functionality Fso-OPPRF , the secret-shared outputs rj,k ∈ F for k ∈ [d] are uniformly random. (2) The second case is IDqj = IDwi for some wi ∈ W and there exists some k ∗ such that |qj,k∗ − wi,k∗ | > δ . According to the correctness of functionality Fso-OPPRF , the secretshared P output rj,k∗ ∈ F is uniformly random. In both cases, rj := k∈[d] rj,k ∈ F is uniformly random. According to the correctness of functionality FPEQT , a union bound shows that the probability of there existing j ∈ [m] such that bj = 1 is at most m/|F|. By setting |F| ≥ m · 2λ , the probability m/|F| ≤ 1/2λ is negligible. The correctness of FOT ensures the receiver learns nothing about qj . We show the protocol’s security in Theorem 3 and the security proof is deferred to Appendix A.3. ∞ Theorem 3. The protocol ΠL FPSI in Figure 12 realizes the functionality FFPSI for L∞ distance in Figure 4 against semi-honest adversaries in the (Fso-OPPRF , FPEQT , FOT )hybrid model.
6.2. Fuzzy PSI for Lp Distance We present the construction of fuzzy PSI for Lp distance, which closely resembles that of L∞ distance. Given the fact that distp (q, w) ≤ δ implies dist∞ (q, w) ≤ δ , this protocol reuses the fuzzy mapping protocol for L∞ distance to generate IDs, with the only modification in the refined filtering. Specifically, two parties invoke functionality Fso-OPPRF , where the receiver sets the key-value pairs as {(IDwi ∥k∥(wi,k + t), |t|p )}i∈[n],k∈[d],t∈[−δ,δ] , and the sender prepares {IDqj ∥k∥qj,k }j∈[m],k∈[d] . Then, two parties get the secret sharing of the distance |wi,k − qj,k |p for each dimension k ∈ [d] or a random value. The following process computes the distance P p distp (qj , wi )p = k∈[d] |wi,k − qj,k | . We note that the
L
p Protocol ΠFPSI Parameters: Distance threshold δ . Input: S inputs Q = {qj }j∈[m] ∈ Ud×m and R inputs W = {wi }i∈[n] ∈ Ud×n . Protocol: 1) S and R invoke sub-protocol ΠFMap , where S inputs Q and R inputs W . S obtains {IDqj }j∈[m] and R obtains {IDwi }i∈[n] . 2) S and R invoke functionality Fso-OPPRF , where R as the sender inputs {(IDwi ∥k∥(wi,k + t), |t|p )}t∈[−δ,δ],i∈[n],k∈[d] and S as the receiver inputs {IDqj ∥k∥qj,k }j∈[m],k∈[d] . S receives S R {rj,k }j∈[m],k∈[d] and R receives {rj,k }j∈[m],k∈[d] . 3) (Optional) S and R invoke functionality FB2A , S where S inputs {rj,k }j∈[m],k∈[d] and R inputs R {rj,k }j∈[m],k∈[d] . S receives {dS j,k }j∈[m],k∈[d] and R receives {dR j,k }j∈[m],k∈[d] . P S 4) For j ∈ [m], S computes dS j := k∈[d] dj,k , and R P R R computes dj := k∈[d] dj,k . 5) S and R invoke functionality FInterval , where S inR puts {dS j }j∈[m] and R inputs {dj }j∈[m] . R receives S R {bj }j∈[m] , where bj := 1{dj + dj ≤ δ p }. 6) S and R invoke functionality FOT , where S inputs {(⊥, qj )}j∈[m] , and R inputs {bj }j∈[m] and receives {zj }j∈[m] . 7) R outputs Z := {zj | bj = 1 for j ∈ [m]}.
Figure 13: Protocol of fuzzy PSI for Lp distance. protocol includes a Boolean-to-arithmetic conversion (B2A) protocol, since the outputs of our so-OPPRF protocol reside in a binary field F2ℓ that does not support computing arithmetic operations of the Lp distance. B2A converts the outputs of so-OPPRF into arithmetic shares, which are suitable for subsequent computation. In addition, unlike the private equality test used in ∞ protocol ΠL FPSI , here we invoke the private interval test protocol [21] to determine whether the distance falls below the threshold δ p . The detailed construction of the protocol is illustrated in Figure 13. We show the correctness as follows. Proof. Correctness. For each qj ∈ Q, if there exists wi ∈ W such that distp (qj , wi ) ≤ δ , then by the correctness of fuzzy mapping for L∞ distance in Theorem 2 and the fact that dist∞ (qj , wi ) ≤ distp (qj , wi ) ≤ δ for any qj , wi , it holds IDqj = IDwi . Then, by the correctness of functionalities Fso-OPPRF and FB2A , it holds dSj,k + dR j,k = P p S R S R |w − q | , and hence d + d = (d + d )= i,k j,k j j j,k j,k k∈[d] P p p |w − q | ≤ δ . Therefore, by the correctness i,k j,k k∈[d] of functionalities FInterval and FOT , the receiver correctly obtains bj = 1 and the corresponding element qj . On the other hand, for each qj ∈ Q, if distp (qj , wi ) > δ in Lp distance for all wi ∈ W , there are three cases due to the false positive of fuzzy mapping. (1) The first case is IDqj ̸= IDwi for any wi ∈ W . According to the correctness S R of functionality Fso-OPPRF , the output rj,k + rj,k ∈ F is S uniformly random for k ∈ [d] . Therefore, r + rjR := j P S R k∈[d] (rj,k + rj,k ) ∈ F is uniformly random. (2) The
Protocol ΠEQSel Parameters: Ideal functionality FMUX and FssPEQT . S Input: S inputs {(eS and R inputs i , vi )}i∈[h] R {(eR , v )} . i∈[h] i i Protocol: 1) S and R invoke FssPEQT , where S inputs {eS i }i∈[h] and h S R inputs {eR i }i∈[h] . S receives {bi }i∈[h] ∈ {0, 1} , h and R receives {bR } ∈ {0, 1} . i i∈[h] S 2) S and R invoke FMUX , where S inputs {(bS i , vi )}i∈[h] R R S and R inputs {(bi , vi )}i∈[h] . S receives {ti }i∈[h] and R receives {tR i }i∈[h] L. P S 3) S computes bS := i∈[h] bS tS and R i , t := L P i∈[h]R i R R R computes b := i∈[h] bi , t := i∈[h] ti . 4) S randomly samples rS and R randomly samples rR . 5) S and R invoke FMUX , where S inputs (bS , tS − rS ) and R inputs (bR , tR − rR ). S receives mS and R receives mR . 6) S outputs z S := mS + rS . R outputs z R := mR + rR .
Figure 14: Protocol of random equality-conditional selection. second case is IDqj = IDwi but dist∞ (qj , wi ) > δ . There exists k ∗ ∈ [d] such that |qj,k∗ − wi,k∗ | > δ . Then, according to the correctness of functionality Fso-OPPRF , the S R output rj,k ∗ + rj,k ∗ ∈ F is uniformly random. Similarly, P S R R S rj + rj := k∈[d] (rj,k + rj,k ) ∈ F is uniformly random. As a result, in the first two cases, the probability of rjS + rjR ≤ δ is at most δ p /|F|. By the correctness of functionality Finterval , for any j ∈ [m], a union bound shows that the probability of there existing j ∈ [m] such that bj = 1 is at most mδ p /|F|. By setting |F| ≥ mδ p 2λ , the probability mδ p /|F| ≤ 1/2λ is negligible. The correctness of functionality FOT ensures the receiver learns nothing about qj . (3) The third case is IDqj = IDwi and dist∞ (qj , wi ) ≤ δ for some wi ∈ W . By the correctness of functionalities Fso-OPPRF and FB2A , dSj,k + dR |wi,k − qj,k |p , it holds j,k = P P S R R S dj + dj = k∈[d] (dj,k + dj,k ) = k∈[d] |wi,k − qj,k |p = distp (qj , wi )p > δ p . The correctness of FInterval and FOT ensure the receiver learns nothing about qj . We show the protocol’s security in Theorem 4, and the security proof is deferred to Appendix A.4. L
p Theorem 4. The protocol ΠFPSI in Figure 13 realizes the functionality FFPSI for Lp distance in Figure 4 against semihonest adversaries in the (Fso-OPPRF , FB2A , FInterval , FOT )hybrid model.
7. Fuzzy PSI with Prefix Optimization In this section, we present how to optimize our fuzzy PSI framework using prefix techniques [12], [16], [18] for the large distance threshold δ . In the previous section, our fuzzy PSI achieves linear complexity with respect to δ in both communication and computation. With prefix optimizations, we reduce the complexity to O (log δ).
Protocol ΠFMap-Prefix Parameters: Threshold δ . Prefix parameter µ′ = 1 + log δ and µ = 2 + log δ . Input: S inputs Q = {qj }j∈[m] ∈ Ud×m and R inputs W = {wi }i∈[n] ∈ Ud×n . Protocol: 1) S runs LocalMapPrefix (Q) and obtains ({pidqj }j∈[m] , ListS ). R runs LocalMapPrefix (W ) and obtains ({pidwi }i∈[n] , ListR ). 2) S and R sample secret shares kS , kR of the PRF key, respectively. 3) For j ∈ [m], k ∈ [d], S computes {qj,k,h }h∈[µ] := AllPrefix(qj,k , µ′ ). S and R invoke functionality Fso-OPPRF , where R as the sender inputs ListR and S as the receiver inputs {k∥qj,k,h }j∈[m],k∈[d],h∈[µ] . S reS ceives {eS qj ,k,h ∥vqj ,k,h }j∈[m],k∈[d],h∈[µ] and R receives R {eR ∥v } qj ,k,h qj ,k,h j∈[m],k∈[d],h∈[µ] . 4) For j ∈ [m], k ∈ [d], S and R invoke sub-protocol S ΠEQSel , where S inputs {(eS qj ,k,h , vqj ,k,h )}h∈[µ] and R S receives rqj ,k , and R inputs {(eqj ,k,h , vqRj ,k,h )}h∈[µ] and receives rqRj ,k . P 5) For j ∈ [m], S computes rqSj := k∈[d] rqSj ,k , and R P computes rqRj := k∈[d] rqRj ,k . 6) S and R invoke Fsi-OPRF , where R as the sender inputs (kR , {rqRj }j∈[m] ), and S as the receiver inputs (kS , {rqSj + pidqj }j∈[m] ) and learns {IDqj }j∈[m] . 7) Symmetrically, for i ∈ [n], k ∈ [d], R computes {wi,k,h }h∈[µ] := AllPrefix(wi,k , µ′ ). S and R invoke functionality Fso-OPPRF , where S as the sender inputs ListS and R as the receiver inputs {k∥wi,k,h }i∈[n],k∈[d],h∈[µ] . S receives S and R receives {eS wi ,k,h ∥vwi ,k,h }i∈[n],k∈[d],h∈[µ] R {eR wi ,k,h ∥vwi ,k,h }i∈[n],k∈[d],h∈[µ] . 8) For i ∈ [n], k ∈ [d], S and R invoke sub-protocol S ΠEQSel , where S inputs {(eS wi ,k,h , vwi ,k,h )}h∈[µ] and R R S )}h∈[µ] receives rwi ,k , and R inputs {(ewi ,k,h , vw i ,k,h R and receives rwi ,k . P S S , and R 9) For i ∈ [n], S computes rw := k∈[d] rw i i ,k P R R computes rwi := k∈[d] rwi ,k . 10) S and R invoke Fsi-OPRF , where S as the sender inS puts (kS , {rw } ), and R as the receiver inputs i i∈[n] R R (k , {rwi + pidwi }i∈[n] ) and learns {IDwi }i∈[n] .
Figure 15: Protocol of fuzzy mapping with prefix optimization.
7.1. Optimized Fuzzy Mapping At a high level, by incorporating prefix techniques [12], [16], [18] into our framework, the sender in the so-OPPRF protocol does not need to program the entire interval [qj,k − δ, qj,k + δ] of size 2δ + 1, but only O (log δ) prefixes that together cover the interval. On the receiver side, this modification introduces an additional O (log δ) evaluations of so-OPPRF, since there are O (log δ) candidate prefixes that may match. Consequently, the overall complexity is reduced from O(δ) to O(log δ).
∞ Protocol ΠL FPSI-Prefix Parameters: Distance threshold δ . Prefix parameters µ′ = 1 + log δ and µ = µ̂ = 2 + log δ . Input: S inputs Q = {qj }j∈[m] ∈ Ud×m and R inputs W = {wi }i∈[n] ∈ Ud×n .
Protocol: 1) S and R invoke sub-protocol ΠFMap-Prefix , where S inputs Q and R inputs W . S obtains {IDqj }j∈[m] and R obtains {IDwi }i∈[n] . 2) For i ∈ [n], k ∈ [d], R computes {wi,k,h }h∈[µ̂] := Decompose(wi,k − δ, wi,k + δ). 3) For j ∈ [m], k ∈ [d], S computes {qj,k,h }h∈[µ] := AllPrefix(qj,k , µ′ ). 4) S and R invoke functionality Fso-OPPRF , where R inputs {(IDwi ∥k∥wi,k,h , 0)}i∈[n],k∈[d],h∈[µ̂] and S inputs {IDqj ∥k∥qj,k,h }j∈[m],k∈[d],h∈[µ] . S receives S {eS and R receives j,k,h ∥vj,k,h }j∈[m],k∈[d],h∈[µ] R {eR ∥v j,k,h j,k,h }j∈[m],k∈[d],h∈[µ] . 5) For j ∈ [m], k ∈ [d], S and R invoke sub-protocol S ΠEQSel , where S inputs {(eS j,k,h , vj,k,h )}h∈[µ] and reR R S )}h∈[µ] and ceives tj,k , and R inputs {(ej,k,h , vj,k,h R receives tj,k . P S 6) For j ∈ [m], S computes tS j := k∈[d] tj,k , and R P R R computes tj := k∈[d] tj,k . 7) S and R invoke functionality FPEQT , where S inR puts {tS j }j∈[m] and R inputs {−tj }j∈[m] . R receives R {bj }j∈[m] where bj := 1{tS = −t j j }. 8) S and R invoke functionality FOT , where S inputs {(⊥, qj )}j∈[m] , and R inputs {bj }j∈[m] and receives {zj }j∈[m] . 9) R outputs Z := {zj | bj = 1 for j ∈ [m]}.
Figure 16: Protocol of fuzzy PSI with prefix optimization for L∞ distance.
We first introduce a new building block, denoted as random equality-conditional selection (EQSel). As illustrated in Figure 14, EQSel takes as input a set of secret shares of {(ei , vi )}i∈[h] from two parties, where ei represents a condition and vi denotes a payload. If there exists i ∈ [h] such that ei = 0, the protocol outputs the associated payload vi ; otherwise, it outputs a random value. Note that in our applications, there exists at most one ei equal to 0. We instantiate this protocol using secret-shared private equality test [48] and secret-shared multiplexer [52]. We present our optimized fuzzy mapping protocol in Figure 15. The main difference over our non-prefix fuzzy mapping protocol is that for each wi,k , the receiver needs to prepare µ candidate prefixes for the invocation of so-OPPRF, where the sender sets the programmed values of qj,k ’s prefixes as 0∥rj,k . Subsequently, both parties receive µ secret shares from so-OPPRF and then invoke EQSel on them to select rj,k or a random value depending on whether there is a matched prefix. The remaining part of the protocol keeps the same as ΠFMap .
7.2. Optimized Fuzzy PSI for Lp∈[1,∞] Distance We present our fuzzy PSI protocol with prefix optimization for L∞ distance. The optimized protocol for Lp distance is presented in Appendix B.3. Since our ΠFMap-prefix achieves the same functionality as ΠFMap , we only need to redesign the remaining part of the fuzzy PSI protocol (i.e., the refined filtering phase). Similarly, we use the prefix representation of the interval of size 2δ + 1 to reduce the number of key-value pairs for the refined filtering. With prefix optimization, the sender extends its every single input to µ prefixes in order to match the prefixes of the receiver. Therefore, both parties obtain µ outputs from the so-OPPRF for each dimension of a single element where at most one of these µ prefixes will match. We then use our EQSel protocol again to select the matched prefix, and the output is either the associated value or a random value. The detailed protocol is shown in Figure 16. The security L∞ ∞ proof of protocol ΠL FPSI-Prefix follows that of protocol ΠFPSI in Section 6.1. We omit it due to limited space.
8. Evaluation 8.1. Experimental Setup We implement our protocols in C++ and our code is available at https://github.com/Th0masAndy/FPSI. All experiments are conducted on a server running Ubuntu 22.04, equipped with two AMD EPYC 9555 64-core processors and 512 GB of RAM. The sender and receiver are emulated as two separate threads within a single process. Each experiment is repeated five times, and the average values are reported. 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. In Appendix C, we further evaluate the performance under varying bandwidth and latency settings. We compare our protocols with the state-of-the-art linear-complexity fuzzy PSI schemes [14], [16], as they rely on the same assumption as ours and support highdimensional inputs. For a fair comparison, we re-execute their publicly available implementations under the same experimental environment as ours. Below, we detail the implementation components of our protocols. For OKVS, we adopt the implementation from [6]. The implementations of si-OPRF and so-OPRF are built upon the MPC-friendly PRF proposed by [46]. We use silent OT from the libOTe library [53], and the implementations of ssPEQT and PEQT are based on the protocols from [48]. For the prefix-related algorithms, we use the implementation of [16].
8.2. Performance of Fuzzy PSI We evaluate the performance of our fuzzy PSI protocols in Section 6 and compare them with the state-of-the-art
TABLE 2: The communication (MB) and running time (s) of fuzzy PSI for L∞ , L1 and L2 . “—” indicates out-of-memory. “Ours” denotes our fuzzy PSI protocols in Section 6. The best results are marked in green. m=n
28 212 216
28 212 216
28 212 216
(d, δ) (16, 16) (4, 32) Comm. Time Comm. Time L∞ Distance 8.6 92.1 16.6 45.5 7.8 5.4 173.6 11.8 46.8 2.9 0.3 17.1 0.4 9.4 0.3 144.6 1473.9 282.5 727.3 132.7 85.4 2777.0 181.2 749.3 46.4 2.0 215.8 3.0 93.2 1.4 2269.5 23581.9 4637.7 11636.5 2132.4 1406.1 44431.4 2945.4 11988.4 737.6 25.0 3396.0 42.0 1432.0 19.0 L1 Distance 8.3 92.2 16.6 45.6 7.7 7.2 244.2 14.7 71.2 4.0 0.4 18.4 0.5 9.9 0.3 143.2 1475.4 282.6 729.2 129.6 116.7 3908.1 223.5 1138.3 61.3 2.1 235.3 3.5 98.7 1.6 2299.7 23606.9 4593.3 11667.5 2091.3 1833.3 62529.1 3646.7 18212.9 995.8 27.8 3700.2 46.9 1516.2 20.2 L2 Distance 8.6 92.3 16.6 45.7 7.9 7.6 279.6 14.5 84.8 4.6 0.4 18.4 0.5 9.9 0.4 143.2 1476.9 283.8 731.1 132.5 117.7 4474.2 231.3 1356.0 72.6 2.2 235.5 3.5 99.2 1.6 2321.1 23630.9 4585.5 11697.5 2127.9 1930.9 71588.3 3799.7 21696.1 1159.7 27.8 3708.2 47.7 1526.1 20.4
(4, 16) Comm. Time
(8, 16) Comm. Time
(8, 32) Comm. Time
(16, 32) Comm. Time
Gao et al. [14] Dang et al. [16] Ours Gao et al. [14] Dang et al. [16] Ours Gao et al. [14] Dang et al. [16] Ours
23.2 43.5 7.3 370.9 695.8 60.5 5934.1 11132.6 908.7
4.4 3.1 0.3 73.2 43.3 1.3 1195.7 707.3 17.2
46.2 86.9 10.6 738.5 1389.5 112.3 11816.7 22232.2 1737.6
90.7 93.5 14.7 1451.3 1496.5 177.6 23221.5 23943.8 2784.7
15.1 5.7 0.4 253.9 91.3 2.2 4197.1 1447.8 28.9
181.2 186.9 25.2 2899.5 2990.9 346.5 — 47854.6 5491.5
30.5 12.1 0.5 507.2 190.7 3.7 — 3150.7 49.7
Gao et al. [14] Dang et al. [16] Ours Gao et al. [14] Dang et al. [16] Ours Gao et al. [14] Dang et al. [16] Ours
23.3 61.2 7.8 372.4 978.2 66.1 5959.1 15650.7 990.9
4.2 3.8 0.3 70.7 57.9 1.4 1210.6 930.8 17.9
46.3 122.2 11.3 740.1 1954.8 122.5 11841.7 31276.8 1893.8
90.8 142.2 15.4 1453.3 2274.6 187.8 23252.5 36393.2 2942.9
14.9 7.6 0.5 258.1 120.4 2.5 4165.0 1954.8 31.5
181.3 284.2 26.6 2901.4 4547.1 366.0 — 72753.9 5797.7
30.4 15.6 0.5 506.9 244.3 4.1 — 3888.1 55.8
Gao et al. [14] Dang et al. [16] Ours Gao et al. [14] Dang et al. [16] Ours Gao et al. [14] Dang et al. [16] Ours
23.4 70.1 7.8 373.9 1122.0 66.3 5983.1 17951.5 998.8
4.4 4.0 0.4 72.7 63.1 1.4 1223.9 1009.4 18.6
46.4 140.0 11.4 741.6 2239.4 122.7 11865.7 35830.4 1901.8
91.0 169.0 15.5 1455.2 2703.5 188.2 23282.5 43255.6 2952.8
15.1 8.9 0.4 259.9 132.6 2.5 4134.8 2115.1 31.7
181.5 337.4 26.6 2903.3 5398.4 366.4 — 86374.7 5807.7
30.6 16.0 0.6 509.4 253.3 4.0 — 4332.7 55.1
Protocol
protocols [14], [16]. The results are presented in Table 2, where we set the input sizes to m = n = 28 , 212 , 216 , the dimension to d = 4, 8, 16, and the distance threshold to δ = 16, 32. We do not use prefix optimizations, since for these small distance thresholds our non-prefix protocols are more efficient. The performance of prefix optimizations for large thresholds is presented in the next section. As shown in Table 2, our protocol for L∞ distance achieves a 3∼13× improvement in communication efficiency and a 9∼145× improvement in computational efficiency, outperforming all previous protocols. Specifically, when m = n = 216 , d = 8, and δ = 16, our protocol consumes 13× less communication than [16] and 7× less than [14]. When m = n = 216 , d = 8, and δ = 32, our protocol is 50× faster than [16] and 145× faster than [14]. We note that our protocols achieve better improvement for larger-scale inputs, since the overhead of the underlying silent OT [41] can be amortized. We also present the results for L1 and L2 distances, which are commonly used metrics. Compared with [16], our protocol achieves up to an 80× improvement in running time and a 19× reduction in communication cost. Moreover, our protocols for L1 and L2 distances incur only a minor overhead compared to that of L∞ distance, whereas [16] nearly doubles its overall cost. Under limited network conditions, where the time for communication dominates the total running time, we provide the results in Appendix C.
8.3. Performance of Fuzzy PSI with Prefix Optimization
We report the performance of our fuzzy PSI protocols with prefix optimization for large distance threshold δ . We set relatively large δ as {24 , 26 , 28 , 210 }. As shown in Table 3, our optimized protocols exhibit desirable performance gains for large distance thresholds δ . Overall, compared with the state-of-the-art work [16], we achieve a 7∼10× improvement in communication efficiency and a 13∼38× improvement in computational efficiency. We note that our non-prefix protocols still exhibit competitive performance compared to [16], especially in computation efficiency. We also compare our optimized protocols with our nonprefix protocols. For δ ≥ 64, our optimized protocols significantly reduce the communication overhead. For instance, when δ = 1024, it lowers the communication cost by 11× compared to the non-prefix protocols, while reducing the running time by approximately half. However, our nonprefix protocols still achieve better runtime performance for δ ≤ 256, since the optimized protocols introduce additional operations such as conditional selection. We provide the performance under different network settings in Appendix C. Since our optimized protocol significantly reduces communication overhead, its overall efficiency further improves under limited network conditions.
TABLE 3: The communication (MB) and running time (s) of fuzzy PSI with prefix optimizations for large threshold δ . We fix m = n = 212 and d = 8. “—” indicates out-of-memory. “Ours” denotes our fuzzy PSI protocols in Section 6 and “Ours-prefix” denotes our protocols with prefix optimizations in Section 7. The best results are marked in green. Metric
L∞
L1
L2
Protocol Gao et al. [14] Dang et al. [16] Ours Ours-prefix Gao et al. [14] Dang et al. [16] Ours Ours-prefix Gao et al. [14] Dang et al. [16] Ours Ours-prefix
δ = 16 Comm. Time 738.5 151.5 1389.5 86.2 112.3 1.8 184.8 5.4 740.1 143.4 1954.8 113.4 122.5 2.1 252.2 7.0 741.6 144.3 2239.4 126.6 122.7 2.1 385.2 9.7
δ = 64 Comm. Time 2876.9 496.6 1605.1 95.6 308.3 2.6 225.7 5.7 2879.3 483.3 2487.7 152.6 318.5 2.9 295.9 7.2 2881.5 490.6 2818.4 175.5 319.4 2.9 440.3 9.7
δ = 256 Comm. Time 11430.5 1850.6 2581.0 156.9 1093.1 7.2 289.1 7.9 11433.6 1840.1 3695.2 216.6 1103.5 7.0 367.7 9.6 11436.6 1856.3 4248.0 303.1 1104.6 7.3 534.0 11.9
δ = 1024 Comm. Time — — 2795.0 164.6 4235.8 19.7 366.2 10.0 — — 4479.7 241.5 4246.5 20.3 456.6 10.9 — — 5572.5 572.7 4247.8 21.0 682.6 15.1
9. Discussion
11. Acknowledgment
Limitations. Our work still has the following limitations. First, similar to prior fuzzy PSI protocols [13], [14], [16], [17], [18], our protocol relies on certain assumptions about the input distribution. These assumptions are typically parameterized by the distance threshold δ . While such parameters are well-defined in theoretical analysis, determining appropriate values for real-world datasets remains challenging. Second, it remains unclear how to obtain malicious security without substantially compromising efficiency. A natural approach is to instantiate our construction using maliciously secure OT [54], [55] and authenticated secret sharing based on IT-MACs [56], [57]. However, a key technical challenge is how to efficiently verify that the OKVS encoding is wellformed and consistent. Future Work. We outline several directions for future research. First, it is of interest to design fuzzy PSI protocols under weaker or more flexible assumptions, such as relaxing distribution constraints or supporting one-sided assumptions, while maintaining comparable efficiency. Second, although existing fuzzy PSI protocols guarantee correctness under ideal assumptions, it remains an open problem to quantify and evaluate the impact when these assumptions are violated in practice (e.g., when elements are closer than expected or exhibit collisions). Developing robustness and accuracy guarantees in such settings is an important direction for future work.
This work was supported by the Nanyang Technological University Centre in Computational Technologies for Finance (NTU-CCTF). It was also supported by Lee Kong Chian Chair Professorship, Singapore Management University. It was also supported by 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. 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.
10. Conclusion In this work, we present a novel modular design for fuzzy PSI based on symmetric primitives. Our protocol is built upon a new building block termed so-OPPRF, achieving linear complexity with respect to the input size m, n, the dimension d, and the distance threshold δ . We further optimize the protocol by incorporating prefix techniques, and reduce its complexity to logarithmic in δ . Experimental results demonstrate that our protocols outperform linearcomplexity state-of-the-art works, significantly improving both computation and communication efficiency.
12. Ethics considerations This work provides effective solutions for the fuzzy private set intersection task, encouraging researchers to pay more attention to the privacy of data analysis. The experiments in this paper are all based on public datasets and do not contain any personal or illegal information. We believe that our research was done ethically.
13. LLM usage considerations This paper used the LLM solely to assist with grammar checking and language polishing. The LLM did not contribute any conceptual ideas, methodological innovations, experimental designs, or analytical insights to this work. All intellectual contributions originate from the authors. All data provided to the LLM for linguistic refinement contain no sensitive, personal, or ethically problematic information.
References [1]
C. Meadows, “A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party,” in 1986 IEEE Symposium on Security and Privacy. IEEE, 1986, pp. 134–134.
[2]
M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set intersection,” in International conference on the theory and applications of cryptographic techniques. Springer, 2004, pp. 1–19.
[3]
C. Dong, L. Chen, and Z. Wen, “When private set intersection meets big data: an efficient and scalable protocol,” in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, 2013, pp. 789–800.
[20] D. Bui, G. Garimella, P. Miao, and P. V. L. Pham, “New framework for structure-aware psi from distributed function secret sharing,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2025, pp. 294–326. [21] A. Chakraborti, G. Fanti, and M. K. Reiter, “Distance-aware private set intersection,” in 32nd USENIX Security Symposium (USENIX Security 23), 2023, pp. 319–336.
[4]
B. Pinkas, T. Schneider, G. Segev, and M. Zohner, “Phasing: Private set intersection using permutation-based hashing,” in 24th USENIX Security Symposium (USENIX Security 15), 2015, pp. 515–530.
[22] L. Chmielewski and J.-H. Hoepman, “Fuzzy private matching,” in 2008 Third International Conference on Availability, Reliability and Security. IEEE, 2008, pp. 327–334.
[5]
B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai, “Psi from paxos: Fast, malicious private set intersection,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2020, pp. 739–767.
[23] Q. Ye, R. Steinfeld, J. Pieprzyk, and H. Wang, “Efficient fuzzy matching and intersection on private datasets,” in International Conference on Information Security and Cryptology. Springer, 2009, pp. 211– 228.
[6]
S. Raghuraman and P. Rindal, “Blazing fast psi from improved okvs and subfield vole,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022, pp. 2505–2517.
[24] P. Indyk and D. Woodruff, “Polylogarithmic private approximations and efficient matching,” in Theory of Cryptography Conference. Springer, 2006, pp. 245–264.
[7]
M. Hao, W. Liu, L. Peng, H. Li, C. Zhang, H. Chen, and T. Zhang, “Unbalanced circuit-psi from oblivious key-value retrieval,” in 33rd USENIX Security Symposium (USENIX Security 24), 2024, pp. 6435– 6451.
[8]
[9]
Google, “Better password protections in chrome how it works,” 2019, last accessed 11 November 2025. [Online]. Available: https://security.googleblog.com/2019/12/ better-password-protections-in-chrome.html L. Shen, X. Chen, D. Wang, B. Fang, and Y. Dong, “Efficient and private set intersection of human genomes,” in 2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, 2018, pp. 761–764.
[10] E. Uzun, S. P. Chung, V. Kolesnikov, A. Boldyreva, and W. Lee, “Fuzzy labeled private set intersection with applications to private real-time biometric search,” in 30th USENIX Security Symposium (USENIX Security 21), 2021, pp. 911–928. [11] G. Garimella, M. Rosulek, and J. Singh, “Structure-aware private set intersection, with applications to fuzzy matching,” in Annual International Cryptology Conference. Springer, 2022, pp. 323–352. [12] G. Garimella, B. Goff, and P. Miao, “Computation efficient structureaware psi from incremental function secret sharing,” in Annual International Cryptology Conference. Springer, 2024, pp. 309–345. [13] A. van Baarsen and S. Pu, “Fuzzy private set intersection with large hyperballs,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2024, pp. 340– 369. [14] Y. Gao, L. Qi, X. Liu, Y. Luo, and L. Wang, “Efficient fuzzy private set intersection from fuzzy mapping,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2024, pp. 36–68. [15] C. Zhang, Y. Chen, Y. Cao, Y. Bai, S. Li, J. Lin, A. Wang, and X. Wang, “Fast fuzzy psi from symmetric-key techniques,” Cryptology ePrint Archive, 2025. [16] C. Dang, X. Zhou, and B. Liang, “Efficient fuzzy psi based on prefix representation,” in Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, 2025, pp. 2204–2218.
[25] E.-O. Blass and G. Noubir, “Assumption-free fuzzy psi via predicate encryption,” Cryptology ePrint Archive, 2025. [26] C. Cho, D. Dachman-Soled, and S. Jarecki, “Efficient concurrent covert computation of string equality and set intersection,” in Cryptographers’ Track at the RSA Conference. Springer, 2016, pp. 164– 179. [27] W. Chongchitmate, S. Lu, and R. Ostrovsky, “Approximate psi with near-linear communication,” Cryptology ePrint Archive, 2024. [28] T. De Vries, H. Ke, S. Chawla, and P. Christen, “Robust record linkage blocking using suffix arrays and bloom filters,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 5, no. 2, pp. 1–27, 2011. [29] E. A. Durham, M. Kantarcioglu, Y. Xue, C. Toth, M. Kuzu, and B. Malin, “Composite bloom filters for secure record linkage,” IEEE transactions on knowledge and data engineering, vol. 26, no. 12, pp. 2956–2968, 2013. [30] X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava, “Composing differential privacy and secure computation: A case study on scaling private record linkage,” in Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, 2017, pp. 1389–1406. [31] A. Inan, M. Kantarcioglu, G. Ghinita, and E. Bertino, “Private record matching using differential privacy,” in Proceedings of the 13th International Conference on Extending Database Technology, 2010, pp. 123–134. [32] B. Khurram and F. Kerschbaum, “Sfour: a protocol for cryptographically secure record linkage at scale,” in 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020, pp. 277–288. [33] R. Wei and F. Kerschbaum, “Cryptographically secure private record linkage using locality-sensitive hashing,” Proceedings of the VLDB Endowment, vol. 17, no. 2, pp. 79–91, 2023. [34] S. Stammler, T. Kussel, P. Schoppmann, F. Stampe, G. Tremper, S. Katzenbeisser, K. Hamacher, and M. Lablans, “Mainzelliste secureepilinker (mainsel): privacy-preserving record linkage using secure multi-party computation,” Bioinformatics, vol. 38, no. 6, pp. 1657–1668, 2022.
[17] L. Piske, J. Singh, N. Trieu, V. Kolesnikov, and V. Zikas, “Distanceaware ot with application to fuzzy psi,” in Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, 2025, pp. 4679–4691.
[35] A. Adir, E. Aharoni, N. Drucker, E. Kushnir, R. Masalha, M. Mirkin, and O. Soceanu, “Privacy-preserving record linkage using local sensitive hash and private set intersection,” in International Conference on Applied Cryptography and Network Security. Springer, 2022, pp. 398–424.
[18] A. van Baarsen and S. Pu, “Fuzzy private set intersection from vole,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2025, pp. 327–360.
[36] K. Zhao, H. Lu, and J. Mei, “Locality preserving hashing,” in Proceedings of the AAAI conference on artificial intelligence, vol. 28, no. 1, 2014.
[19] D. Richardson, M. Rosulek, and J. Xu, “Fuzzy psi via oblivious protocol routing,” Cryptology ePrint Archive, 2024.
[37] J. Leskovec, A. Rajaraman, and J. D. Ullman, Mining of massive data sets. Cambridge university press, 2020.
[38] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970.
[55] L. Roy, “Softspokenot: Quieter ot extension from small-field silent vole in the minicrypt model,” in Annual international cryptology conference. Springer, 2022, pp. 657–687.
[39] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of cryptography conference. Springer, 2006, pp. 265–284.
[56] R. Bendlin, I. Damgård, C. Orlandi, and S. Zakarias, “Semihomomorphic encryption and multiparty computation,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2011, pp. 169–188.
[40] A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher, “Min-wise independent permutations,” in Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, pp. 327–336. [41] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, P. Rindal, and P. Scholl, “Efficient two-round ot extension and silent non-interactive secure computation,” in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019, pp. 291–308. [42] S. Raghuraman, P. Rindal, and T. Tanguy, “Expand-convolute codes for pseudorandom correlation generators from lpn,” in Annual International Cryptology Conference. Springer, 2023, pp. 602–632. [43] V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek, and N. Trieu, “Practical multi-party private set intersection from symmetric-key techniques,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1257–1272. [44] G. Garimella, B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai, “Oblivious key-value stores and amplification for private set intersection,” in Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part II 41. Springer, 2021, pp. 395–425. [45] A. van Baarsen and M. Stevens, “Amortizing circuit-PSI in the multiple sender/receiver setting,” IACR Communications in Cryptology, vol. 1, no. 3, 2024. [46] N. Alamati, G.-V. Policharla, S. Raghuraman, and P. Rindal, “Improved alternating-moduli prfs and post-quantum signatures,” in Annual International Cryptology Conference. Springer, 2024, pp. 274– 308. [47] B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Efficient circuit-based psi with linear communication,” in Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III 38. Springer, 2019, pp. 122–153. [48] P. Rindal and P. Schoppmann, “Vole-psi: fast oprf and circuit-psi from vector-ole,” in Annual international conference on the theory and applications of cryptographic techniques. Springer, 2021, pp. 901–930. [49] D. Boneh, Y. Ishai, A. Passelègue, A. Sahai, and D. J. Wu, “Exploring crypto dark matter: New simple prf candidates and their applications,” in Theory of Cryptography Conference. Springer, 2018, pp. 699–729. [50] I. Dinur, S. Goldfeder, T. Halevi, Y. Ishai, M. Kelkar, V. Sharma, and G. Zaverucha, “Mpc-friendly symmetric cryptography from alternating moduli: Candidates, protocols, and applications,” in Annual International Cryptology Conference. Springer, 2021, pp. 517–547. [51] M. R. Albrecht, A. Davidson, A. Deo, and D. Gardham, “Crypto dark matter on the torus: Oblivious prfs from shallow prfs and tfhe,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2024, pp. 447–476. [52] D. Rathee, M. Rathee, N. Kumar, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Cryptflow2: Practical 2-party secure inference,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, pp. 325–342. [53] P. Rindal and L. Roy, “libOTe: an efficient, portable, and easy to use Oblivious Transfer Library,” https://github.com/osu-crypto/libOTe. [54] K. Yang, C. Weng, X. Lan, J. Zhang, and X. Wang, “Ferret: Fast extension for correlated ot with small communication,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, pp. 1607–1626.
[57] J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra, “A new approach to practical active-secure two-party computation,” in Annual Cryptology Conference. Springer, 2012, pp. 681–700.
Appendix A. Threat Model and Security Proof A.1. Threat Model Similar to prior works [13], [14], [16], [18], we consider static semi-honest probabilistic polynomial-time (PPT) adversaries. Namely, a PPT adversary A passively corrupts either the sender S or the receiver R at the beginning of the protocol and honestly follows the protocol specification. We use the standard simulation-based security definition for secure two-party computation. Our construction invokes multiple sub-protocols, and we use the hybrid model to describe them. By convention, a protocol invoking a functionality F is referred to as the F -hybrid model. We give the formal security definition as follows. Π Definition 5. Let viewΠ S (x, y) and viewR (x, y) be the views of S and R in a protocol Π, respectively, where x is the input of S and y is the input of R. Let out(x, y) be the protocol’s output of both parties and F(x, y) be the functionality’s output. Π is said to securely compute a functionality F in the semi-honest model if for every PPT adversary A there exists PPT simulators SimS and SimR such that for all inputs x and y ,
{viewΠ S (x, y), out(x, y)} ≈c {SimS (x, FS (x, y)), F (x, y)}, {viewΠ R (x, y), out(x, y)} ≈c {SimR (x, FR (x, y)), F (x, y)}.
A.2. Proof of so-OPPRF We give the detailed proof of Theorem 1. Proof. If both parties behave honestly, correctness on programmed points (q, z) ∈ L follows from the correctness of OKVS, since yiS +yiR = OKVS.Decode(D, q)+fiS +fiR = z − Fk (q) + Fk (q) = z . On unprogrammed points x ∈ X , the OKVS encoding D is independent from Fk (x), and thus the value yiS + yiR := Fk (x) + OKVS.Decode(D, x) is indistinguishable from a uniformly random distribution, since Fk (·) is indistinguishable from a random function by definition of FOPRF . We next consider a corrupted sender or receiver. Corrupted sender. We show the simulator ′ SimS (L, {yiS }i∈[n] , OF ): 1) SimS computes D ← OKVS.Encode({(qj , zj − F (qj ))}j∈[m] ), where F (qj ) are randomly sampled.
Functionality FMUX Parameters: Sender S and receiver R. Protocol: 1) Wait for input (x0 , b0 ) from S and (x1 , b1 ) from R. 2) Select r0 randomly, and set r1 = x0 + x1 − r0 if b0 + b1 = 1 otherwise set r1 = −r0 . 3) Output r0 to R and r1 to S .
Figure 17: Functionality of MUX. Functionality FssPEQT Parameters: Sender S and receiver R. Protocol: 1) Wait for input x0 from S and x1 from R. 2) Select r0 randomly, and set r1 = 1 − r0 if x0 = x1 otherwise set r1 = −r0 . 3) Output r0 to R and r1 to S .
Figure 18: Functionality of secret-shared PEQT. For each query x ∈ / {qj }j∈[m] , SimS defines F (x) := F ′ (x) − OKVS.Decode(D, x). ′ 2) SimS appends ({fiS := yiS }i∈[n] , OF , OF ) in the view. We show that the view of adversary simulated by Sim has the identical distribution as its view in the real-world execution. For programmed points qj , it holds F ′ (qj ) = F (qj ) + OKVS.Decode(D, qj ). For unprogrammed points x, the output F (x) := F ′ (x) − OKVS.Decode(D, x) is uniformly random according to the independence property of OKVS. Corrupted receiver. We show the simulator SimR (X, {yiR }i∈[n] ): 1) SimR samples a random OKVS encoding D on m random key-value pairs and appends D in the view. 2) SimR appends {fiR }i∈[n] in the view, where fiR := yiR − OKVS.Decode(D, xi ) for i ∈ [n]. We show that the output by SimR is indistinguishable from the real protocol. By the double obliviousness property of OKVS and the randomness of so-OPRF, the randomly sampled OKVS encoding D is statistically indistinguishable from a real protocol execution. Moreover, fiR has the same distribution in both the real and simulated protocols such that yiR = fiR + OKVS.Decode(D, xi ).
A.3. Proof of Fuzzy PSI for L∞ distance We give the detailed proof of Theorem 3. Proof. Corrupted sender. We show the simulator SimS (Q), which invokes the sub-simulator SimFMap : S 1) SimS invokes SimFMap (Q, ID ) and appends the output Q S to the view, where IDQ is randomly sampled. S 2) SimS randomly samples {rj,k }j∈[m],k∈[d] and appends them to the view.
Protocol ΠgetListp Parameters: {IDwi }i∈[n] , {wi }i∈[n] , p. Denote µ = log δ . Protocol: 1) For i ∈ [n], k ∈ [d], compute {w0,i,k,h }h∈[µ] := Decompose([wi,k − δ, wi,k ]) and {w1,i,k,h }h∈[µ] := Decompose([wi,k + 1, wi,k + δ]). 2) If p = 1: • Listp := {(IDwi ∥k∥σ∥wσ,i,k,h , 0∥|w∗ − wi,k |)}i∈[n],k∈[d],σ∈[0,1],h∈[µ] , where w∗ := UpBound(wσ,i,k,h ) if σ = 0 and w∗ := LowBound(wσ,i,k,h ) otherwise. 3) If p = 2: • Listp := {(IDwi ∥k∥σ∥wσ,i,k,h , 0∥|w∗ − wi,k |∥|w∗ − wi,k |2 )}i∈[n],k∈[d],σ∈[0,1],h∈[µ] , where w∗ := UpBound(wσ,i,k,h ) if σ = 0 and w∗ := LowBound(wσ,i,k,h ) otherwise. 4) Pad Listp into size n · d · 2 · µ and outputs Listp
Figure 19: Protocol for computing list for p = 1 and p = 2. The protocol can extend to arbitrary p. Protocol ΠgetDistancep µ×p , q ∈ U, Parameters: Sender inputs {sS h }h∈[µ] ∈ F µ×p } ∈ F . Functionality σ ∈ {0, 1}. Receiver inputs {sR h h∈[µ] FMult . Denote µ = log δ . Protocol: 1) S computes {qh }h∈[µ] := AllPrefix(q, µ). 2) For h ∈ [µ], S computes eh := |q − UpBound(qh )| if σ = 0 and eh = |q − LowBound(qh )| otherwise. 3) If p = 1: S S • For h ∈ [µ], S computes dh := eh + sh and R R . := s computes dR h h 4) If p = 2: 2 S S S • For h ∈ [µ], S parses sh = sh,1 ∥sh,2 ∈ F and R 2 R R R parses sh = sh,1 ∥sh,2 ∈ F . • For h ∈ [µ], i ∈ [1, p], S and R invoke FMult where S S inputs eh and R inputs sR h,1 . S receives mh and R R receives mh . S 2 S • For h ∈ [µ], S computes dh := eh + 2eh · sh,1 + R S S R R 2mh + sh,2 and dh := 2mh + sh,2 . R 5) S outputs {dS h }h∈[µ] and R outputs {dh }h∈[µ] .
Figure 20: Protocol for computing distance for p = 1 and p = 2. The protocol can extend to arbitrary p.
We show that the output by SimS is indistinguishable from the real protocol. According to the security property of fuzzy mapping in Theorem 2, the simulated view of SimFMap S is indistinguishable from the real execution. Besides, the S only difference is {rj,k }j∈[m],k∈[d] . They are random secret shares in the real protocol according to the so-OPPRF functionality, while they are randomly sampled in the simulated view with the same distribution. Therefore, the output by SimS is indistinguishable from the real protocol. Corrupted receiver. We show the simulator SimR (W, Z), which invokes the sub-simulator SimFMap : R
1) SimR randomly samples IDW . SimR invokes SimFMap (W, IDW ) and appends the output to the view. R R 2) SimR randomly samples {rj,k }j∈[m],k∈[d] and samples a random function F such that F (IDwi ∥k∥(wi,k +t)) = 0 for t ∈ [−δ, δ], i ∈ [n], k ∈ [d]. SimR appends R ({rj,k }j∈[m],k∈[d] , OF ) to the view. 3) SimR uses ⊥ to pad Z to m elements, randomly shuffles the set Z , and sets bj := 0 if zj = 0 and bj := 1 otherwise for j ∈ [m]. SimR appends ({bj }j∈[m] , Z) to the view. We show that the output by SimR is indistinguishable from the real protocol. According to the security property of fuzzy mapping in Theorem 2, the simulated view of SimFMap is indistinguishable from the real execution. MoreR over, the way R obtains the elements in Z is identical to the real execution since the elements in Z are randomly shufR fled. Besides, the only difference is ({rj,k }j∈[m],k∈[d] , OF ). R {rj,k }j∈[m],k∈[d] are random secret shares in the real protocol according to the so-OPPRF functionality, while they are randomly sampled in the simulated view with the same distribution. Then, the function F is constructed in the same manner in the real and simulated executions. Therefore, the output by SimR is indistinguishable from the real protocol.
A.4. Proof of Fuzzy PSI for Lp distance We give the detailed proof of Theorem 4, which is similar to that of Theorem 3. Proof. Corrupted sender. We show the simulator SimS (Q), which invokes the sub-simulator SimFMap : S 1) SimS randomly samples IDQ . SimS invokes (Q, IDQ ) and appends the output to the SimFMap S view. S 2) SimS randomly samples {rj,k }j∈[m],k∈[d] and appends it to the view. 3) SimS randomly samples {dSj,k }j∈[m],k∈[d] and appends it to the view. We show that the output by SimS is indistinguishable from the real protocol. According to the security property of fuzzy mapping in Theorem 2, the simulated view of SimFMap S is indistinguishable from the real execution. Besides, the S only differences are {rj,k }j∈[m],k∈[d] and {dSj,k }j∈[m],k∈[d] . They are random secret shares in the real protocol according to the functionalities Fso-OPPRF and FB2A , while they are randomly sampled in the simulated view with the same distribution. Therefore, the output by SimS is indistinguishable from the real protocol. Corrupted receiver. We show the simulator SimR (W, Z), which invokes the sub-simulator SimFMap : R 1) SimR randomly samples IDW . SimR invokes SimFMap (W, IDW ) and appends the output to the view. R R 2) SimR randomly samples {rj,k }j∈[m],k∈[d] and samples a random function F such that F (IDwi ∥k∥(wi,k +t)) =
L
p Protocol ΠFPSI -Prefix Parameters: Distance threshold δ . Prefix parameters µ′ = log δ and µ = 1 + log δ . Input: S inputs Q = {qj }j∈[m] ∈ Ud×m and R inputs W = {wi }i∈[n] ∈ Ud×n .
Protocol: 1) S and R invoke sub-protocol ΠFMap-Prefix , where S inputs Q and R inputs W . S obtains {IDqj }j∈[m] and R obtains {IDwi }i∈[n] . 2) R invokes ΠgetListp ({IDwi }i∈[n] , {wi }i∈[n] , p) and gets Listp . 3) For j ∈ [m], k ∈ [d], S computes {qj,k,h }h∈[µ] := AllPrefix(qj,k , µ). 4) S and R invoke functionality Fso-OPPRF , where R inputs Listp and S inputs {IDqj ∥k∥σ∥qj,k,h }σ∈[0,1],j∈[m],k∈[d],h∈[µ] . S receives S {eS and R σ,j,k,h ∥vσ,j,k,h }σ∈[0,1],j∈[m],k∈[d],h∈[µ] R receives {eR σ,j,k,h ∥vσ,j,k,h }σ∈[0,1],j∈[m],k∈[d],h∈[µ] . 5) For σ ∈ [0, 1], j ∈ [m], k ∈ [d], h ∈ [µ], S and R S and invoke functionality FB2A , where S inputs vσ,j,k,h R and R receives . S receives sS R inputs vσ,j,k,h σ,j,k,h sR σ,j,k,h . 6) For σ ∈ [0, 1], j ∈ [m], k ∈ [d], S and R invoke ΠgetDistancep , where S inputs ({sS σ,j,k,h }h∈[µ] , qj,k , σ), S R inputs {sR σ,j,k,h }h∈[µ] . S receives {dσ,j,k,h }h∈[µ] and R R receives {dσ,j,k,h }h∈[µ] . 7) For j ∈ [m], k ∈ [d], S and R invoke FEQSel , where S S inputs {eS σ,j,k,h , dσ,j,k,h }σ∈[0,1],h∈[µ] and R inputs S R } , d {eR σ,j,k,h σ∈[0,1],h∈[µ] . S receives rj,k and R σ,j,k,h R receives rj,k . P S 8) For j ∈ [m], S computes rjS := k∈[d] rj,k , and R P R R computes rj := k∈[d] rj,k . 9) For j ∈ [m], S and R invoke functionality FInterval , where S inputs rjS and R inputs rjR . R receives bj := 1(rjS + rjR ≤ δ p ). 10) For j ∈ [m], R and S invoke functionality FOT , where R inputs bj and S inputs (⊥, qj ). R receives OT outputs zj . 11) R outputs Z := {zj | bj = 1 for j ∈ [m]}.
Figure 21: Protocol of fuzzy PSI with prefix optimization for Lp distance. |t|p for t ∈ [−δ, δ], i ∈ [n], k ∈ [d]. SimR appends R ({rj,k }j∈[m],k∈[d] , OF ) to the view. 3) SimR randomly samples {dR j,k }j∈[m],k∈[d] and appends them to the view. 4) SimR uses ⊥ to pad Z to m elements, randomly shuffles the set Z , and sets bj := 0 if zj = 0 and bj := 1 otherwise for j ∈ [m]. SimR appends ({bj }j∈[m] , Z) to the view. We show that the output by SimR is indistinguishable from the real protocol. According to the security property of fuzzy mapping in Theorem 2, the simulated view of SimFMap is indistinguishable from the real exeR cution. Moreover, the way R obtains the elements in Z is identical to the real execution since the elements in Z are randomly shuffled. Besides, the only difference is
TABLE 4: The communication (MB) and running time (s) of fuzzy PSI in Section 6 under different network settings. m=n
δ
16 256 32
16 4096 32
16 65536 32
d
4 8 16 4 8 16 4 8 16 4 8 16 4 8 16 4 8 16
Comm. 7.3 10.6 17.1 9.4 14.7 25.2 60.5 112.3 215.8 93.2 177.6 346.5 908.7 1737.6 3396.0 1432.0 2784.7 5491.5
10Gbps 0.3 0.3 0.4 0.3 0.4 0.5 1.3 2.0 3.0 1.4 2.2 3.7 17.2 25.0 42.0 19.0 28.9 49.7
L∞ 1Gbps 0.4 0.5 0.7 0.6 0.7 0.8 1.8 2.7 4.4 2.2 3.5 6.1 22.4 36.8 65.0 28.5 49.8 92.0
L1
100Mbps 4.8 5.3 5.8 5.1 5.7 6.7 10.4 15.1 25.0 13.4 21.4 37.0 96.9 172.1 319.4 143.0 271.1 511.3
Comm. 7.8 11.3 18.4 9.9 15.4 26.6 66.1 122.5 235.3 98.7 187.8 366.0 990.9 1893.8 3700.2 1516.2 2942.9 5797.7
10Gbps 0.3 0.4 0.5 0.3 0.5 0.5 1.4 2.1 3.5 1.6 2.5 4.1 17.9 27.8 46.9 20.2 31.5 55.8
L2
1Gbps 0.5 0.6 0.8 0.6 0.7 0.9 2.0 3.0 5.0 2.4 3.8 6.7 24.4 39.2 71.0 30.5 53.9 99.2
100Mbps 5.2 5.8 6.2 5.5 6.4 7.1 11.3 16.5 27.5 14.2 22.7 40.3 105.7 190.4 351.1 151.1 284.3 541.9
Comm. 7.8 11.4 18.4 9.9 15.5 26.6 66.3 122.7 235.5 99.2 188.2 366.4 998.8 1901.8 3708.2 1526.1 2952.8 5807.7
10Gbps 0.4 0.4 0.5 0.4 0.4 0.6 1.4 2.2 3.5 1.6 2.5 4.0 18.6 27.8 47.7 20.4 31.7 55.1
1Gbps 0.6 0.6 0.7 0.6 0.7 0.9 2.0 3.0 4.9 2.4 3.9 6.6 24.5 39.5 71.3 31.1 53.8 99.8
100Mbps 5.2 5.8 6.2 5.5 6.4 7.1 11.3 16.5 27.6 14.3 22.7 39.2 106.4 188.3 355.5 155.6 286.6 541.4
TABLE 5: The communication (MB) and running time (s) of fuzzy PSI under different network settings. We fix m = n = 212 and d = 8. “Ours-prefix” denotes our optimized protocol in Section 7 and “Ours” denotes our non-optimized protocol in Section 6. δ
16 64 256 1024
Protocol Ours Ours-prefix Ours Ours-prefix Ours Ours-prefix Ours Ours-prefix
Comm. 112.3 184.8 308.3 225.7 1093.1 289.1 4235.8 366.2
10Gbps 1.8 5.4 2.6 5.7 7.2 7.9 19.7 10.0
L∞ 1Gbps 2.6 6.3 5.1 6.8 15.1 9.0 55.3 9.7
L1
100Mbps 15.1 27.4 33.7 31.2 104.5 38.4 389.7 42.8
Comm. 122.5 252.2 318.5 295.9 1103.5 367.7 4246.5 456.6
R R ({rj,k }j∈[m],k∈[d] , OF , {dR j,k }j∈[m],k∈[d] ). {rj,k }j∈[m],k∈[d] R and {dj,k }j∈[m],k∈[d] are random secret shares in the real protocol according to the functionalities Fso-OPPRF and FB2A , while they are randomly sampled in the simulated view with the same distribution. Then, the function F is constructed in the same manner in the real and simulated executions. Therefore, the output by SimR is indistinguishable from the real protocol.
Appendix B. Details of Fuzzy PSI with Prefix Optimizations B.1. Other Building Blocks We present the functionalities of FMUX and FssPEQT in Figure 17 and Figure 18, respectively. L
p B.2. Sub-protocols for ΠFPSI -Prefix
We present the sub-protocols of our optimized fuzzy PSI Lp protocol ΠFPSI -Prefix in Figure 19 and Figure 20.
B.3. Optimized Fuzzy PSI for Lp Distance With prefix optimization, it is non-trivial to convert L∞ distance to Lp distance. As the interval is broken into
10Gbps 2.1 7.0 2.9 7.2 7.0 9.6 20.3 10.9
L2
1Gbps 3.0 8.4 5.4 8.9 15.7 11.1 55.9 13.1
100Mbps 16.4 35.6 35.5 39.2 109.3 46.9 386.5 55.5
Comm. 122.7 385.2 319.4 440.3 1104.6 534.0 4247.8 682.6
10Gbps 2.1 9.7 2.9 9.7 7.3 11.9 21.0 15.1
1Gbps 3.0 11.6 5.6 12.4 15.5 15.1 56.0 18.9
100Mbps 16.4 49.3 35.3 54.0 106.3 63.1 388.9 78.7
prefixes, we cannot directly compute the distance for every point within the interval; instead, we only know the distance associated with each prefix. Dang et al. [16] addressed this issue by decomposing the distance into two parts. Specifically, the distance between points x and y can be expressed as |x − x∗ | + |x∗ − y|, where x∗ represents either the upper or lower bound of the prefix that x falls into. The value |x − x∗ | can be computed by the sender, while |x∗ − y| can be computed by the receiver, and the two parties then jointly compute the sum of these two distances. We adopt a similar method but realize the same functionality using more efficient MPC primitives to keep consistent with our framework, whereas Dang et al. [16] heavily rely on Paillier encryption. Our modified construction for the key-value pairs is presented in Figure 19 and Figure 20. Lp The detailed protocol for ΠFPSI -Prefix is shown in Figure 21 and its security proof follows Appendix A.4.
Appendix C. Performance under Different Network Settings We provide the performance of our fuzzy PSI protocols and the variants with prefix optimizations under different network settings in Table 4 and Table 5. We set the network to 1 Gbps bandwidth with 40 ms latency and 100 Mbps with 80 ms latency.
Appendix D. Meta-Review The following meta-review was prepared by the program committee for the 2026 IEEE Symposium on Security and Privacy (S&P) as part of the review process as detailed in the call for papers.
D.1. Summary The paper improves the efficiency of a known construction of Fuzzy-PSI where two parties match similar but not necessarily identical elements. It contributes the primitive of an Oblivious Programmable Pseudo-Random Function (OPPRF) with secret shared outputs.
D.2. Scientific Contributions •
Provides a Valuable Step Forward in an Established Field.
D.3. Reasons for Acceptance 1) The paper provides a valuable step forward in the established field of Fuzzy-PSI. It significantly improves the performance of a known construction by contributing a new primitive - an OPPRF with secret shared outputs - which may be of independent interest.