Set size and dimension. FPSI typically builds upon a fuzzy matching sub-protocol that allows a receiver to verify whether the distance between its element and the sender’s element is within a threshold \(\delta\). This sub-protocol can be viewed as a special case of FPSI where both sets contain a single element. A straightforward FPSI construction would perform fuzzy matching for every sender-receiver element pair, resulting in quadratic complexity \(O(mn)\), where \(m\) and \(n\) denote the set sizes of the sender and receiver, respectively.

To reduce the number of fuzzy matching operations, existing FPSI protocols typically rely on distributional assumptions about set elements. The two primary assumptions adopted in the literature are the apart assumption and the separate assumption. The apart assumption requires that the distance between any two elements within a party’s set exceeds \(2\delta d^{1/p}\) (or \(2\delta(d^{1/p}+1)\)), which simplifies to \(2\delta\) and \(4\delta\) for \(L_\infty\) distance. This represents a relatively mild constraint. Under this assumption, spatial hashing techniques [4], [19] can reduce the number of fuzzy matching operations from \(O(mn)\) to \(O(\min\{m,n\} \cdot 2^d)\), making it suitable for low-dimensional setting.

For high-dimensional setting, the stronger separate assumption is adopted, which assumes that for each element, there exists at least one dimension where its distance from all other elements exceeds \(2\delta\). This assumption implies the apart assumption. As shown by van Baarsen and Pu [4], randomly generated sets satisfy the separate assumption with overwhelming probability in dimension \(d\). FPSI protocols based on this assumption typically achieve polynomial dependence on \(d\), making them suitable for high-dimensional settings. Notably, under this assumption, Gao et al. [22] achieved linear complexity in \(d\) for the first time, i.e., \(O(d(m+n))\).

Distance threshold. Fuzzy matching protocols typically rely on an interval testing sub-protocol. For \(L_\infty\) distance, verifying whether the distance between \(d\)-dimensional elements \(\mathbf{q}= (q_1,\ldots,q_d)\) and \(\mathbf{w}= (w_1,\ldots,w_d)\) is within \(\delta\) requires checking that \(|w_k - q_k| \leq \delta\) for every \(k \in [d]\), which is equivalent to testing whether each \(w_k\) lies in the interval \([q_k - \delta, q_k + \delta]\). A straightforward method enumerates all \(t \in [q_k - \delta, q_k + \delta]\) and tests whether \(w_k = t\), resulting in a linear cost of \(O(\delta)\) in the threshold. This approach has been employed in several recent works [4], [22], [26], [29], resulting in \(O(d\delta)\) complexity for fuzzy matching.

To improve efficiency, Chakraborti et al. [5] introduced a prefix-based method that represents the interval \([q_k - \delta, q_k+\delta]\) using only \(O(\log \delta)\) prefixes. Interval testing then reduces to checking whether any prefix of \(w_k\) matches the prefix set of the interval, achieving an optimal logarithmic complexity of \(O(\log \delta)\) per dimension. While this reduces the interval testing cost from \(O(\delta)\) to \(O(\log\delta)\), its application to fuzzy matching typically introduces an additional factor of \(O((\log\delta)^d)\) [21], [27], [28], [30], leading to an overall complexity of \(O(d\log\delta+(\log\delta)^d)\) for \(L_\infty\).

Moreover, unlike \(L_\infty\) distance, general Minkowski distances \(L_{p\in[1,\infty)}\) do not support independent per-dimension interval testing, making prefix techniques considerably more challenging to apply. Consequently, nearly all FPSI protocols for \(L_{p\in[1,\infty)}\) distance achieve only linear complexity \(O(\delta)\) in the threshold [4], [22], [26], [28], [29]. A recent exception is the work by Dang et al. [30], which proposed a prefix-based fuzzy matching protocol for \(L_{p\in[1,\infty)}\) distances with complexity \(O(dp\log\delta+(2\log\delta)^d)\). However, their construction still retains an exponential term \(O((2\log\delta)^d)\) and, more critically, contains a security flaw that we have identified (See Appendix 8 for more details). Therefore, constructing a secure fuzzy matching protocol for general \(L_{p\in[1,\infty)}\) distances with complexity \(O(dp\log\delta)\) remains an open problem.

Public-key vs. symmetric-key. Early private set intersection (PSI) protocols relied on public-key primitives such as DDH [31] or additively homomorphic encryption (AHE) [18], thus suffered from limited efficiency. The emergence of OT extension [32], [33] enabled efficient generation of numerous OT instances using only lightweight symmetric-key operations and a small number of base OTs. This breakthrough shifted the design paradigm, leading to modern PSI protocols [14], [15] that achieve orders of magnitude improvement over public-key-based approaches. A similar transition is now underway in FPSI, where recent work aims to replace public-key operations with OT and symmetric-key techniques.

However, many current FPSI protocols still heavily rely on inefficient DDH [4] or AHE [22], [30]. Recently, several concurrent works [26]–[29] have employed OT and symmetric-key operations to enhance FPSI efficiency. Despite this progress, these constructions have not achieved optimal asymptotic efficiency. They either lack support for general \(L_{p\in[1,\infty)}\) distance [27], [29], or exhibit linear dependency on the threshold \(\delta\) for \(L_{p\in[1,\infty)}\) distance [26], [29].

Equality Conditional Sum/Inner-Product Share. We introduce two new cryptographic protocols as the core building blocks of our construction: Equality Conditional Sum Share (ECSS) and Equality Conditional Inner-Product Share (ECIPS). The ECSS protocol enables efficient computation of \(L_\infty\) distance, while ECIPS supports \(L_{p\in[1,\infty)}\) distance. Both protocols can be efficiently implemented using OT and symmetric-key operations and may be of independent interest.

New Fuzzy Matching for Both \(L_\infty\) and \(L_{p\in[1,\infty)}\) Distances. Built on ECSS and ECIPS, we propose the first fuzzy matching protocol based on OT and symmetric-key operations that supports both \(L_\infty\) and \(L_{p\in[1,\infty)}\) distances while achieving exact logarithmic dependence on the distance threshold \(\delta\). Existing solutions either exhibit strictly worse asymptotic complexities [26], [28], [29] or rely on expensive AHE [30].

Fuzzy PSI Protocols for Low-Dimensional Spaces. By combining our fuzzy matching protocol with spatial hashing and cuckoo hashing techniques, we construct FPSI protocols for both \(L_\infty\) and \(L_{p\in[1,\infty)}\) distances in low-dimensional settings. Our protocols rely on apart assumption [4], where the distance between any two elements within a party’s set must exceed \(2\delta d^{1/p}\), or alternatively \(2\delta(d^{1/p}+1)\). For \(L_\infty\) distance, these bounds simplify to \(2\delta\) and \(4\delta\), respectively. The corresponding asymptotic complexities are provided in Table ¿tbl:tab:compare?.

Fuzzy PSI Protocols for High-Dimensional Spaces. For high-dimensional setting, we avoid the exponential \(O(2^d)\) cost of spatial hashing by employing an interactive fuzzy mapping method, specifically a distributed ID generation (dIDG) protocol. Consistent with prior works [4], [22], [30], our high-dimensional protocols rely on the separate assumption. Asymptotic complexities are summarized in Table ¿tbl:tab:compare?.

Experimental Evaluation. We implement our FPSI protocols for \(L_{p\in[1,\infty]}\) distance and conduct comprehensive comparisons with state-of-the-art FPSI protocols [22], [27], [30]. Experimental results show that our protocols achieve significant performance improvements, with runtime up to \(43.7\times\) faster and communication reduced by up to \(31.3\times\).

Fuzzy Matching for \(L_\infty\). An intuitive idea for an \(L_\infty\) fuzzy matching protocol is described below. Here, a sender holds \(\mathbf{q}\) and a receiver holds \(\mathbf{w}\), and the receiver will learn whether \(\mathsf{dist}_\infty(\mathbf{q},\mathbf{w})\leq\delta\). The protocol employs AHE and an Oblivious Key-Value Store (OKVS) scheme [11]. The basic idea is for the receiver to encode a ciphertext of \(0\) for every integer within \(\delta\) in each dimension of its element, namely \(E_k:=\mathsf{Encode}(\{(w_k+v,\mathsf{Enc}_{pk}(0))\}_{v\in[-\delta,\delta]})\) for \(k\in[d]\). The sender then decodes using its element \(\mathbf{q}\) and sums the results as \(c:=\sum_{k\in[d]}\mathsf{Decode}(E_k,q_k)\). If \(\mathsf{dist}_\infty(\mathbf{q},\mathbf{w})\leq\delta\), the sum \(c\) is a ciphertext of \(0\); otherwise, it is random. Next, the sender adds a random plaintext \(r\) to \(c\) using additive homomorphism, sends the result, and the receiver decrypts to verify if it matches \(r\). This basic method, adopted in prior works [4], [22], incurs communication and computation costs linear in \(\delta\).

To reduce the overhead, the protocol can be optimized via prefix representation, which constitutes the core contribution of [30]. Instead of enumerating all integers in the interval, the receiver encodes only the \(l=O(\log\delta)\) prefixes representing the interval. Correspondingly, the sender decodes using the prefixes of its own element. Concretely, the receiver first computes the prefix representation \(\{w_{k,1}^*,\dots,w_{k,l}^*\}\) of each interval \([w_k-\delta,w_k+\delta]\) and constructs an OKVS \(E_k:=\mathsf{Encode}(\{(w_{k,v}^*,\mathsf{Enc}_{pk}(0))\}_{v\in[l]})\) for each dimension \(k\in[d]\). The sender computes its own prefixes \(\{q_{k,1}^*,\dots,q_{k,l'}^*\}\), picks a random value \(a_k\) per dimension, and computes for each prefix the value \(u_{k,v}:=\mathsf{Decode}(E_k,q_{k,v}^*)+\mathsf{Enc}_{pk}(a_k)\). Note that if \(q_{k,v}^*\) matches some \(w_{k,v'}^*\), we have \(|q_k-w_k|\leq \delta\) and \(u_{k,v}\) is a ciphertext of \(a_k\). Then, the sender sends \(\{u_{k,v}\}_{k\in[d],v\in[l']}\) along with \(r=H(\sum_{k\in[d]} a_k)\), where \(H\) is a universal hash function. Finally, the receiver exhaustively checks all combinations \(\mathbf{v}=(v_1,\dots,v_d)\in[l']^d\) by testing whether \(r = H(\sum_{k} \mathsf{Dec}_{sk}(u_{k,v_k}))\).

The avove protocol suffers from three main issues. First, it relies on expensive AHE operations, which impacts efficiency. Second, the receiver must traverse all \(O((\log\delta)^d)\) possible prefix combinations, introducing significant computational overhead. Third and most critically, the protocol is insecure. The security flaw originates in the sender’s masking step. For each dimension \(k\), the same random mask \(a_k\) is added to all prefix decoding results \(\{\mathsf{Decode}(E_k,q_{k,v}^*)\}_{v\in[l']}\). This leaks information about the sender’s input. A detailed attack demonstrating this vulnerability is provided in Appendix 8.

We now describe our approach to address these issues. For the first problem, our key observation is that we can achieve the same functionality using additive secret sharing (ASS) instead of AHE. In this approach, the receiver encodes \(\{(w_{k,v}^*, r_k)\}_{v \in [l]}\) into an OKVS, where \(r_k\) is a random value picked by the receiver. The sender subsequently decodes it using its own prefixes \(\{q_{k,v}^*\}_{v\in[l']}\) to obtain the values \(r_{k,v}'\). If \(q_k\) lies within the interval \([w_k - \delta, w_k + \delta]\), there exists some \(v \in [l']\) such that \(r_{k,v}' = r_k\); otherwise, with overwhelming probability, \(r_{k,v}' \neq r_k\) for every \(v \in [l']\). Thus, the pair \((r_{k,v}', -r_k)\) forms a conditional zero-sharing: it yields shares of zero exactly when the interval test succeeds, and shares of a random value otherwise. A challenge arises because OKVS guarantees obliviousness only when encoded values are uniformly random, so we cannot directly send an OKVS encoding a fixed value. We resolve this by employing an Oblivious Programmable PRF (OPPRF) [34] instead of OKVS. This leverages the standard technique of using an OPRF to generate a one-time pad, thereby ensuring the necessary randomness for the encoded values. To tackle the remaining efficiency and security concerns, we introduce a new primitive named Equality Conditional Sum (ECS). In the ECS functionality, both the sender and receiver input sets of two-dimensional vectors, denoted \(A = \{ \mathbf{a}_{k,v} = (a_{k,v}^0, a_{k,v}^1) \}_{k \in [d], v \in [l]}\) and \(B = \{ \mathbf{b}_{k,v} = (b_{k,v}^0, b_{k,v}^1) \}_{k \in [d], v \in [l]}\), where \(k\) indexes dimensions and \(v\) indexes prefixes. The component with superscript \(1\) is used for comparison, while the component with superscript \(0\) is used for summation. The functionality identifies, for each dimension \(k\), an index \(v_k^* \in [l]\) such that \(a_{k,v_k^*}^1 = b_{k,v_k^*}^1\)¹; if no such index exists, a random \(v_k^*\) is selected. It then computes the sum \(\mathsf{Sum} := \sum_{k \in [d]} (a_{k, v_k^*}^0 + b_{k, v_k^*}^0)\) and delivers \(\mathsf{Sum}\) to the receiver.

Afger the OPPRF evaluation, both parties proceed to invoke the ECS functionality. In this phase, the sender acts as the ECS receiver, providing input vectors in which both components are set to its OPPRF outputs, that is, \(b_{k,v}^0 = b_{k,v}^1 := r_{k,v}'\). Meanwhile, the receiver participates as the ECS sender, constructing input vectors with the first component set to zero and the second component containing the random values generated during OPPRF encoding: \(a_{k,v}^0 := 0\), \(a_{k,v}^1 := r_k\). This construction ensures that the sender learns \(\sum_{k \in [d]} r_k\) if and only if a zero-sharing condition is satisfied in every dimension, which is equivalent to \(|w_k - q_k| \leq \delta\) for all \(k \in [d]\). To complete the verification, the receiver also computes \(\mathsf{Rand} := \sum_{k \in [d]} r_k\), and the parties check whether the sender’s output from ECS equals \(\mathsf{Rand}\). Therefore, a secure ECS protocol based on OT and symmetric cryptographic primitives, with an overhead of only \(O(d \log \delta)\), is sufficient to address all the challenges mentioned above.

Equality Conditional Sum (Share). We now present the construction of our ECS protocol, along with a variant called ECS Share (ECSS) that outputs secret shares of \(\mathsf{Sum}\) rather than delivering the result directly to the receiver. This ECSS variant is useful in our high-dimensional FPSI construction.

The general idea of our ECS protocol is to let the receiver obtain \(v_k^*\) when \(a_{k,v_k^*}^1 = b_{k,v_k^*}^1\); otherwise, the receiver gets a random \(v_k^*\). The receiver subsequently calculates and sums over these \(v_k^*\) values. Specifically, the protocol proceeds through the following steps. First, both parties execute a secret-shared Private Equality Test (ssPEQT) on all pairs \((a_{k,v}^1, b_{k,v}^1)\), obtaining secret-shared bits \(e_{k,v}^\mathcal{S}\) and \(e_{k,v}^\mathcal{R}\) such that \(e_{k,v}^\mathcal{S} \oplus e_{k,v}^\mathcal{R} = 1\) if and only if \(a_{k,v}^1 = b_{k,v}^1\). Next, each party locally XORs its bits across all \(v\), yielding \(\tilde{e}_{k,0}^\mathcal{S} := \bigoplus_{v\in[l]} e_{k,v}^\mathcal{S}\) and \(\tilde{e}_{k,0}^\mathcal{R} := \bigoplus_{v\in[l]} e_{k,v}^\mathcal{R}\). Consequently, \(\tilde{e}_{k,0}^\mathcal{S} \oplus \tilde{e}_{k,0}^\mathcal{R} = 1\) exactly when there exists a \(v_k^* \in [l]\) satisfying \(a_{k,v_k^*}^1 = b_{k,v_k^*}^1\). If such \(v_k^*\) exists, let \(\eta=\log l\) and define \(S_\alpha:=\{x_\eta\dots x_{\alpha+1} 1 x_{\alpha-1}\dots x_1:x_1,\dots,x_{\eta}\in\{0,1\}\}\), the parties compute \(\tilde{e}_{k,\alpha}^\mathcal{S} := \bigoplus_{i\in S_\alpha} e_{k,i}^\mathcal{S}\) and \(\tilde{e}_{k,\alpha}^\mathcal{R} := \bigoplus_{i\in S_\alpha} e_{k,i}^\mathcal{R}\). It can be simply verified that \((\tilde{e}_{k,\alpha}^\mathcal{S},\tilde{e}_{k,\alpha}^\mathcal{R})\) forms the secret shares of the \(\alpha\)-th bit of \(v_k^*\). By assembling all \(\eta\) bits, the parties learn exactly the shares of \(v_k^*\). Specifically, the sender learns \(v_k^\mathcal{S}\) and the receiver learns \(v_k^\mathcal{R}\), with \(v_k^\mathcal{S} \oplus v_k^\mathcal{R} = v_k^*\). Now, the goal is for the receiver to learn \(v_k^*\) only if such an index exists; otherwise it should receive a random index. This is achieved via a 2-choice-bit OT: the sender samples a random index \(r_k \leftarrow [l]\) and inputs \((v_k^\mathcal{S}, r_k)\) if \(\tilde{e}_{k,0}^\mathcal{S}=1\), and \((r_k, v_k^\mathcal{S})\) otherwise. The receiver inputs \(\tilde{e}_{k,0}^\mathcal{R}\). This ensures the receiver reconstructs the correct \(v_k^\mathcal{S}\) precisely when \(\tilde{e}_{k,0}^\mathcal{S} \oplus \tilde{e}_{k,0}^\mathcal{R} = 1\).

After the receiver obtains \(v_k^*\), the parties invoke a 1-out-of-\(l\) OT. In this step, the sender selects random masks \(\{\mathsf{mask}_k\}_{k\in[d]}\) subject to \(\sum_{k\in[d]} \mathsf{mask}_k = 0\), and inputs \(\{a_{k,v}^0 + \mathsf{mask}_k\}_{v\in[l]}\). The receiver inputs \(v_k^*\) and receives \(\gamma_k = a_{k,v_k^*}^0 + \mathsf{mask}_k\). The receiver then computes \(\mathsf{Sum} := \sum_{k\in[d]} (\gamma_k + b_{k,v_k^*}^0)\). For ECSS, the sender instead picks all masks arbitrarily and sets its own share as \(-\sum_{k\in[d]} \mathsf{mask}_k\).

The steps described above correctly implement the ECS functionality, but they introduce a security issue that could compromise sender privacy. Specifically, allowing the receiver to learn each \(v_k^*\) directly could reveal information about the sender’s set. To address this issue, we propose to let the receiver learn a permuted index \(\pi(v_k^*)\) instead, where \(\pi\) is a random permutation over \([l]\) chosen by the sender and kept hidden from the receiver. This is achieved using a Permute + Share (PS) protocol [35], [36]. In the PS protocol, the sender inputs a permutation \(\pi\), the receiver inputs a vector \(\mathbf{b}_k = (b_{k,1}^1,\dots,b_{k,l}^1)\), and both parties receive additive shares of the permuted vector. Concretely, the sender obtains \(\mathbf{b}^\mathcal{S} = (b_{k,1}^\mathcal{S},\dots,b_{k,l}^\mathcal{S})\) and the receiver obtains \(\mathbf{b}^\mathcal{R} = (b_{k,1}^\mathcal{R},\dots,b_{k,l}^\mathcal{R})\), such that \(b_{k,v}^\mathcal{S} + b_{k,v}^\mathcal{R} = b_{k,\pi(v)}^1\). The sender then computes \(\tilde{a}_{k,v}^1 := a_{k,\pi(v)}^1 - b_{k,v}^\mathcal{S}\). At this stage, the parties can invoke ssPEQT on \(\tilde{a}_{k,v}^1\) and \(b_{k,v}^\mathcal{R}\); one can verify that \(\tilde{a}_{k,v}^1 = b_{k,v}^\mathcal{R}\) if and only if \(a_{k,\pi(v)}^1 = b_{k,\pi(v)}^1\). Subsequently, following the steps previously outlined, the parties obtain secret shares of \(\pi(v_k^*)\).

Combining the above techniques yields the ECS (and ECSS) protocol. For \(L_{p\in[1,\infty)}\) distance, we introduce a similar component called Equality Conditional Inner-Product Share (ECIPS), which is constructed analogously to ECSS but replaces the local summation with an inner product protocol. Details are provided in Section 3.2.

Fuzzy Matching for \(L_{p\in[1,\infty)}\). Previous works [4], [22] encode \(\{(w_k + v, \mathsf{Enc}_{pk}(|v|^p))\}_{v\in[-\delta,\delta]}\) into an OKVS. If \(q_k \in [w_k-\delta, w_k+\delta]\), the sender decodes precisely the ciphertext of \(|w_k - q_k|^p\). Using additive homomorphism, a ciphertext of \(\mathsf{dist}_p(\mathbf{q},\mathbf{w})^p = \sum_{k\in[d]}|w_k - q_k|^p\) can then be obtained. This method, however, requires enumerating all values in the interval. Dang et al. [30] proposed a new approach leveraging prefix representation. Assuming \(q_k \leq w_k\), their core idea is to find a public midpoint \(q_k \leq w' \leq w_k\) such that \(|w_k - q_k| = |w_k - w'| + |q_k - w'|\). The receiver encodes ciphertext of \(|w_k - w'|\) into the OKVS, and the sender locally adds \(|q_k - w'|\) after decoding. They observed that the right endpoint of the prefix-generated interval satisfies this property². More concretely, let \(\{w_{k,1}^*, \dots, w_{k,l}^*\}\) be the prefix representation of \([w_k-\delta, w_k]\), and let \(q_{k,v'}^*\) be a prefix of \(q_k\) that matches some \(w_{k,v}^*\). The receiver encodes \(\{w_{k,v}^*, \mathsf{Enc}(|w_k - \mathsf{UpBound}(w_{k,v}^*)|)\}_{v\in[l]}\), where \(\mathsf{UpBound}(w_{k,v}^*)\) denotes the right endpoint of the interval corresponding to prefix \(w_{k,v}^*\). The sender computes the ciphertext of \(|w_k - q_k|\) as \(\mathsf{Decode}(E, q_{k,v'}^*) + |q_k - \mathsf{UpBound}(q_{k,v'}^*)|\). To obtain the ciphertext of \(|w_k - q_k|^p\), the receiver encodes for each \(t\in[p]\) the values \(\mathsf{Enc}(|w_k - \mathsf{UpBound}(w_{k,v}^*)|^t)\). The sender then uses the binomial formula to derive the ciphertext of \(|w_k - q_k|^p\) as \(\sum_{t\in[0,p]}\binom{p}{t}\mathsf{Enc}(|w_k - \mathsf{UpBound}(w_{k,v}^*)|^t)\cdot |q_k - \mathsf{UpBound}(q_{k,v'}^*)|^{p-t}\).

The prefix technique expands the sender’s decoding attempts per dimension by a multiplicative factor \(l = O(\log \delta)\). Dang et al. [30] employed a method analogous to their \(L_\infty\) construction to sum across dimensions, but it inherits the same shortcomings of insecurity and an additional \(O((\log \delta)^d)\) factor. To resolve these issues, our initial step is again to adopt ASS in place of AHE. In particular, the parties obtain secret shares of \(|w_k - w'|\), denoted \(\llbracket |w_k - w'| \rrbracket_\mathcal{S}\) and \(\llbracket |w_k - w'| \rrbracket_\mathcal{R}\), rather than a ciphertext. Consequently, both parties should locally apply the binomial formula to their shares to compute shares of \(|w_k - q_k|^p\), instead of having the sender perform this computation alone. This presents a challenge because the sender alone knows the binomial coefficients \(\binom{p}{t}|q_k - w'|^{p-t}\), and revealing them would leak information about its input.

We address this by reframing the computation as an inner product problem. Define the vectors \[\begin{align} \label{aaa} \mathbf{a}^0 &= \bigl(0, \llbracket |w_k - w'| \rrbracket_\mathcal{R}, \dots, \llbracket |w_k - w'|^p \rrbracket_\mathcal{R}\bigr), \\ \mathbf{b}^0 &= \bigl(1, \llbracket |w_k - w'| \rrbracket_\mathcal{S}, \dots, \llbracket |w_k - w'|^p \rrbracket_\mathcal{S}\bigr), \\ \mathbf{b}^1 &= \bigl(|q_k - w'|^{p}, \binom{p}{1}|q_k - w'|^{p-1}, \dots, 1\bigr). \end{align}\tag{1}\] Here, \(\mathbf{a}^0\) is known to the receiver, and \(\mathbf{b}^0,\mathbf{b}^1\) are known to the sender. The binomial computation thus reduces to computing the inner product \(\langle \mathbf{a}^0 + \mathbf{b}^0, \mathbf{b}^1 \rangle\). This can be implemented using an inner product protocol of length \(p+1\), which can in turn be realized via \(p+1\) instances of Oblivious Linear Evaluation (OLE) protocol.

To eliminate the \(O((\log \delta)^d)\) expansion, we introduce a new primitive called Equality Conditional Inner-Product Share (ECIPS), analogous to ECSS. In ECIPS, the sender inputs \(A = \{ \mathbf{a}_{k,v}=(\mathbf{a}_{k,v}^0, a_{k,v}^2) \}_{k \in [d], v \in [l]}\) and the receiver inputs \(B = \{ \mathbf{b}_{k,v} = (\mathbf{b}_{k,v}^0, \mathbf{b}_{k,v}^1, b_{k,v}^2) \}_{k \in [d], v \in [l]}\). The superscript \(2\) components are used for equality comparison, while the superscript \(0,1\) components are used for the inner product. For each dimension \(k\), the functionality identifies an index \(v_k^* \in [l]\) such that \(a_{k,v_k^*}^2 = b_{k,v_k^*}^2\); if none exists, a random \(v_k^*\) is chosen. It then computes the inner product sum \(\mathsf{IPSum} := \sum_{k \in [d]} \langle \mathbf{a}_{k, v_k^*}^0 + \mathbf{b}_{k, v_k^*}^0, \mathbf{b}_{k, v_k^*}^1\rangle\) and outputs secret shares of \(\mathsf{IPSum}\) to the two parties.

Similar to our \(L_\infty\) distance protocol, we first let the participants obtain the conditional additive sharing of \(|w_k-q_k|^t\) for \(t\in[p]\) via an OPPRF. Denote this sharing by \((r_{k,t},\,r_{k,v,t}')\), that is, if the prefix \(q_{k,v}^*\) of \(q_k\) equals some prefix of the interval \([w_k-\delta,w_k]\)³, then \(r_{k,t}+r_{k,v,t}'=|w_k-w'|^t\), otherwise the shares are random. In addition, the parties also generate a conditional zero sharing, denoted \((r_{k,p+1},r_{k,v,p+1}')\), for later equality testing. With these shares, the sender defines \(\mathbf{b}^0_{k,v}:=(1,r'_{k,v,1},\dots,r'_{k,v,p}),\mathbf{b}^1_{k,v}:=(\binom{p}{0}|q_k-\mathsf{UpBound}(q_{k,v}^*)|^p,\dots,\binom{p}{p-1}|q_k-\mathsf{UpBound}(q_{k,v}^*)|^1,1),b_{k,v}^2:=r'_{k,v,p+1}\), and the receiver defines \(\mathbf{a}^0_{k,v}:=(0,r_{k,1},\dots,r_{k,p}),a_{k,v}^2:=r_{k,p+1}\). The two parties then invoke the ECIPS functionality on these inputs, receiving outputs \(\mathsf{Rand}_\mathcal{S}\) and \(\mathsf{Rand}_\mathcal{R}\). By the functionality of ECIPS, if \(\forall k\in[d], |q_k-w_k|\leq \delta\), then \(\mathsf{Rand}_\mathcal{S} + \mathsf{Rand}_\mathcal{R} = \sum_{k\in[d]}|w_k-q_k|^p =\mathsf{dist}_p(\mathbf{w},\mathbf{q})^p\). Now, the parties can thus complete \(L_p\) fuzzy matching by checking whether \(\mathsf{Rand}_\mathcal{S} \in [-\mathsf{Rand}_\mathcal{R},\, -\mathsf{Rand}_\mathcal{R} + \delta^p]\) via the fuzzy matching for interval functionality [5], [22].

The ECIPS construction follows a pattern similar to ECSS, with overhead \(O(dp\log\delta)\). Further details are provided in Section 3.2.

Fuzzy PSI for Low Dimensional Spaces. We illustrate the construction using FPSI for \(L_\infty\) distance. The approach for \(L_{p\in[1,\infty)}\) distances follows a similar pattern. Fuzzy matching corresponds to the special case of FPSI where each party holds a single element. When both parties have multiple elements, spatial hashing techniques [4], [19], [21], [28], [30] are commonly employed in low-dimensional settings to reduce the number of pairwise comparisons. This method requires the points of the parties to be at least \(2\delta\) or \(4\delta\) apart for successful OKVS/OPPRF encoding. The core idea is to partition the space into a grid of cells with side length \(2\delta\). For each of its elements, the sender assigns as an identifier (ID) the coordinates of the cell containing that element. The receiver, for each of its elements, considers all cells that intersect the \(\delta\)-radius ball centered at the element, yielding \(2^d\) IDs per element. This encoding guarantees that if \(\mathsf{dist}(\mathbf{w}_i, \mathbf{q}_j) \leq \delta\), the ID sets of \(\mathbf{w}_i\) and \(\mathbf{q}_j\) intersect.

Once the ID sets are computed, the receiver encodes its IDs into an OKVS. Concretely, for each element \(\mathbf{w}_i\), each of its \(2^d\) associated IDs \(\{id_{\mathbf{w}_i,t}\}_{t\in[2^d]}\), the receiver encodes \(\{(id_{\mathbf{w}_i,t} || (w_{i,k}+v),\; \mathsf{Enc}_{pk}(0)\}_{i\in[n],t\in[2^d],v\in[-\delta,\delta]}\). The sender, for each of its elements \(\mathbf{q}_i\), decodes using the query \(id_{\mathbf{q}_i} || q_{i,k}\). This ensures that only when the IDs match does the sender obtain a \(0\)-ciphertext (or, when using OPPRF, shares of \(0\)). When the prefix optimization is applied, the receiver concatenates each ID with the corresponding prefix before encoding, and the sender similarly appends prefixes to its decoding queries. Because each dimension of each sender element requires \(l = O(\log \delta)\) decoding attempts, the sender must examine all \(O((\log \delta)^d)\) possible prefix combinations.

As previously noted, eliminating the \(O((\log\delta)^d)\) factor requires the parties to run an ECS protocol, which thereby introduces an interaction phase after OPPRF. In contrast, prior traversal-based methods avoided such interaction by having the sender locally enumerate all possible summation items. This interaction, however, raises a new challenge: the receiver must correctly match its encoded shares with the corresponding decoding results from the sender to form valid inputs for the ECS.

To overcome this challenge, we employ Simple/Cuckoo hashing [6]. Specifically, the sender inserts its elements into a Cuckoo hash table using each element’s ID as the hash key. In parallel, the receiver inserts its elements into a Simple hash table, encoding shares of \(0\) in each bin. Crucially, under the apart assumption, this ensures that in each bin of the receiver’s table, at most one element lies within distance \(\delta\) of sender’s element. Thus, ECS can be performed bin-by-bin, resolving the alignment problem introduced by departing from purely local traversal.

Nevertheless, the introduction of Cuckoo hashing also reveals the sender’s hashing positions, which leaks information about its entire set. We mitigate this leakage by incorporating a Permute+Share (PS) protocol [35]. The sender locally chooses a random permutation and uses the PS protocol to jointly permute the order of bins with the receiver, thereby hiding the original cuckoo hashing order. We further propose an optimization based on our newly introduced shared OPRF (sOPRF) functionality. Using sOPRF, the parties can realize a shared OPPRF where the receiver’s PRF shares directly serve as the corresponding evaluation shares for the sender. In this setting, the parties only need to run ECS for non-empty bins, and the PS step can be omitted entirely. Additional details are provided in Sections 5.1.2 and 5.2.2.

Fuzzy PSI for High Dimensional Spaces. Under the apart assumption, spatial hashing incurs a \(2^d\) blow-up, as the receiver must generate \(2^d\) IDs per element. Gao et al. [22] introduced a distributed ID generation (dIDG) protocol with expansion rate \(1\) under the stronger separate assumption, generating only one ID per element for both parties.

Roughly speaking, their idea assigns to each element \(\mathbf{q}\) an ID defined as \({id}_{\mathbf{q}} := F_Q(\mathbf{q}) + F_W(\mathbf{q})\), where \(F_Q(\cdot)\) and \(F_W(\cdot)\) are functions constructed such that for any close pair \(\mathsf{dist}(\mathbf{q}, \mathbf{w}) \leq \delta\), we have \(F_{Q}(\mathbf{q})=F_Q(\mathbf{w})\) and \(F_W(\mathbf{q})=F_W(\mathbf{w})\). Critically, the function \(F_Q(\cdot)\) (resp. \(F_W(\cdot)\)) is keyed by the sender’s set \(Q\) (resp. receiver’s set \(W\)). Since each party holds only its own key, the protocol requires the receiver to obliviously evaluate \(F_Q(\cdot)\) on its own set \(W\), and symmetrically, the sender to obliviously evaluate \(F_W(\cdot)\) on \(Q\). Taking the receiver side as an example, \(F_Q\) is constructed as follows. For each dimension \(k\), a random value \(r_k\) is assigned to each projection interval \([q_k-\delta, q_k+\delta]\), and overlapping intervals in the same dimension are merged and assigned the same \(r_k\). Then \(F_Q(\mathbf{w}) = \sum_{k=1}^d r_k\), where \(r_k\) corresponds to the interval containing \(w_k\). This construction, however, introduces collisions: distinct \(\mathbf{w}_1 \neq \mathbf{w}_2\) may yield \(F_Q(\mathbf{w}_1) = F_Q(\mathbf{w}_2)\), revealing proximity information. To eliminate this leakage, Gao et al. [22] incorporate a DH key exchange, defining the final ID as \(id_\mathbf{w} := (F_Q(\mathbf{w}) + F_W(\mathbf{w}))^{sk_s \cdot sk_r}\), where \(sk_s\) and \(sk_r\) are secret DH keys held by the sender and receiver. The receiver thus obtains \(id_\mathbf{w}\) without learning \(F_Q(\mathbf{w})\) directly, thereby concealing collisions.

The construction of Gao et al. [22] incurs a cost of \(O(d\delta(m+n))\). Dang et al. [30] adopt a similar approach but incorporate a prefix technique, reducing complexity to \(O(d\log\delta(m+n))\). However, we find their construction remains insecure. Beyond the earlier mentioned insecurity due to mask reuse, we identify a further security flaw in their distributed ID generation. Gao et al. [22] define the final ID as \({id}_\mathbf{w}= (F_Q(\mathbf{w}) + F_W(\mathbf{w}))^{sk_s \cdot sk_r}\), which involves symmetric operations from both parties. In contrast, Dang et al. [30] effectively set \({id}_\mathbf{w}:= F_Q(\mathbf{w})\), omitting both the receiver’s \(F_W\) evaluation and the DH step. This simplification reintroduces the collision leakage that the DH exchange was designed to prevent. A full analysis is given in Appendix 8. Additionally, we note that both protocols in [22], [30] still rely on relatively inefficient AHE.

To address these issues, we design a dIDG protocol based on OT and symmetric-key primitives. The core idea is to compute all intermediate values in secret‑shared form. Both Gao et al. [22] and Dang et al. [30] use an OKVS to encode AHE ciphertexts of the random values \(r_k\). Our first step is also to replace AHE with ASS. Correspondingly, we replace OKVS with an OPPRF. To incorporate the prefix technique, the receiver must be able to identify which prefix decodes correctly. Fortunately, our previously introduced ECSS functionality exactly fulfills this requirement: we first run an OPPRF, followed by an ECSS protocol, so that the parties obtain additive shares of \(F_Q(\mathbf{w})\). The receiver then locally adds its own \(F_W(\mathbf{w})\) to obtain shares of \(F_Q(\mathbf{w})+F_W(\mathbf{w})\). The next step is to derive the final IDs. In prior work, a DH key exchange is used to compute \(id_{\mathbf{w}} = (F_Q(\mathbf{w})+F_W(\mathbf{w}))^{sk_s \cdot sk_r}\), which requires expensive group exponentiation. We abstract this operation as the evaluation of a weak pseudorandom function \(F_{sk}(x)=x^{sk}\), so that the final ID can be expressed as \[id_{\mathbf{w}} := F_{sk_s}\!\bigl(F_{sk_r}(F_Q(\mathbf{w})+F_W(\mathbf{w}))\bigr).\] To avoid exponentiation, we introduce a new primitive called shared oblivious PRF (sOPRF), a variant of OPRF in which both the input and the output are additively secret‑shared. By invoking two sequential sOPRF instances on the shares of \(F_Q(\mathbf{w})+F_W(\mathbf{w})\), the parties finally obtain shares of \(id_{\mathbf{w}}\), which can then be opened to the receiver.

Once the dIDG protocol is executed, the parties proceed with the same operations as in our low‑dimensional FPSI protocol, but now using the IDs produced by dIDG instead of spatial‑hashing‑based IDs. This substitution removes the \(2^d\) factor inherent in spatial hashing. The complete protocol is described in Section 6.

The remaining question is how to construct an efficient sOPRF. We find that the recent shared‑output OPRF of Alamati et al. [37], built from OT and symmetric‑key operations, offers a promising starting point. We revisit their protocol and introduce a simple yet crucial twist to additionally support shared input, yielding our sOPRF construction. See Section 4 for the full description.

Correctness. For all \(A\subseteq \mathcal{K}\times \mathcal{V}\) with distinct keys:

Obliviousness. For all distinct \(\{x_1^0,\dots,x_n^0\}\) and \(\{x_1^1,\dots,x^1_n\}\), if \(\mathsf{Encode}\) does not output \(\perp\) for \(\{x_1^0,\dots,x_n^0\}\) or \(\{x_1^1,\dots,x_n^1\}\), then the following distributions are computationally indistinguishable:

\(t\)-Randomness [26]. For any \(A= \{(x_1,y_1), \dots, (x_n,y_n)\}\) and for all distinct \(\{x_i^*\}_{i\in[t]}\) satisfying \(x_i^* \notin \{x_1,\dots,x_n\},i\in[t]\), the distribution of \(\{\mathsf{Decode}(E,x_i^*)\}_{i\in[t]}\) is statistically indistinguishable to that of uniform distribution over \(\mathcal{V}^t\), where \(E\leftarrow \mathsf{Encode}(A)\).

Correctness. For any \(\mathbf{q}\in Q\) and \(\mathbf{w}\in W\), if \(\mathsf{dist}(\mathbf{q},\mathbf{w})\leq \delta\), then \(\mathsf{ID}_\mathbf{q}\cap \mathsf{ID}_\mathbf{w}\neq \emptyset\), where \(\mathsf{st}\leftarrow \mathsf{Setup}(Q,W), \mathsf{ID}_\mathbf{q}\leftarrow \mathsf{IDGen}_{\mathcal{S}}(\mathbf{q},\mathsf{st}),\) \(\mathsf{ID}_\mathbf{w}\leftarrow \mathsf{IDGen}_{\mathcal{R}}(\mathbf{w},\mathsf{st})\).

Distinctiveness. \(\forall i,i'\in [n],i\ne i'\), the probability of \(\mathsf{ID}_{\mathbf{w}_i}\cap \mathsf{ID}_{\mathbf{w}_{i'}} \ne \emptyset\) is negligible, where \(\mathsf{st}\leftarrow \mathsf{Setup}(Q,W),\mathsf{ID}_{\mathbf{w}_i}\leftarrow \mathsf{IDGen}_{\mathcal{R}}(\mathsf{st},\mathbf{w}_{i}),\mathsf{ID}_{\mathbf{w}_{i'}}\leftarrow \mathsf{IDGen}_{\mathcal{R}}(\mathsf{st},\mathbf{w}_{i'})\).

Randomness. For any \(Q = \{\mathbf{q}_j\}_{j\in[m]}\subseteq \mathbb{U}^{d}, W = \{\mathbf{w}_i\}_{i\in[n]}\subseteq \mathbb{U}^{d}\), the distribution of \(\{\mathsf{ID}_\mathbf{q}\}_{\mathbf{q}\in Q}\) and \(\{\mathsf{ID}_\mathbf{w}\}_{\mathbf{w}\in W}\) is statistically indistinguishable to that of uniform distribution, where \(\mathsf{st}\leftarrow \mathsf{Setup}(Q,W), \mathsf{ID}_\mathbf{q}\leftarrow \mathsf{IDGen}_{\mathcal{S}}(\mathbf{q},\mathsf{st}),\mathsf{ID}_\mathbf{w}\leftarrow \mathsf{IDGen}_{\mathcal{R}}(\mathbf{w},\mathsf{st}),\mathbf{q}\in Q, \mathbf{w}\in W\).

Silence. The output of algorithm \(\mathsf{Setup}\) is \(\perp\). In other words, the algorithms \(\mathsf{IDGen}_{\mathcal{S}}(\mathbf{q},\mathsf{st})\) and \(\mathsf{IDGen}_{\mathcal{R}}(\mathbf{w},\mathsf{st})\) do not require a common input and work independently.

Correctness. Let \(E_k\) and \(v_k^*\) be defined as in Figure 11. For \(k \in [d], v \in [l]\), the correctness of PS and ssPEQT ensures that: \[e_{k,v}^\mathcal{S} \oplus e_{k,v}^{\mathcal{R}} = 1 \Longleftrightarrow a^1_{k,\pi_k(v)} = b^1_{k,\pi_k(v)}.\] By the correctness of the secure OR functionality, we have: \[\tilde{e}^\mathcal{S}_{k,0} \oplus \tilde{e}^\mathcal{R}_{k,0} = 1 \Longleftrightarrow \exists \tilde{v}_k \in [l] \text{ such that } a^1_{k,\pi_k(\tilde{v}_k)} = b^1_{k,\pi_k(\tilde{v}_k)}.\] From the correctness of \(\mathsf{ShareTrans}\), \(\tilde{e}^{\mathcal{S}}_k\) and \(\tilde{e}^{\mathcal{R}}_k\) form shares of \(\tilde{v}_k = \bigoplus_{i \in \pi_k^{-1}(E_k)} i = \pi_k^{-1}(v_k^*)\) if \(\tilde{e}^\mathcal{S}_{k,0} \oplus \tilde{e}^\mathcal{R}_{k,0} = 1\); otherwise, they form shares of \(0\). The OT in Step 7 ensures \(\mathcal{R}\) learns \(\tilde{v}_k = \pi_k^{-1}(v_k^*)\) if the condition holds, or a random value otherwise. Therefore, the final sum is computed correctly: \[\begin{align} \mathsf{Sum} &= \sum_{k \in [d]} \left( b^{\mathcal{R},0}_{k,\tilde{v}_k} + \gamma_k \right) \\ &= \sum_{k \in [d]} \left( b^{\mathcal{R},0}_{k,\tilde{v}_k} + \tilde{a}_{k,\tilde{v}_k}^0 + \mathsf{mask}_k \right) \\ &= \sum_{k \in [d]} \left( b^{\mathcal{R},0}_{k,\tilde{v}_k} + a^0_{k,\pi_k(\tilde{v}_k)} + b^{\mathcal{S},0}_{k,\tilde{v}_k} \right) \\ &= \sum_{k \in [d]} \left( a^0_{k,v_k^*} + b^0_{k,v_k^*} \right) \end{align}\]

Complexity. When using state-of-the-art PS [36] and ssPEQT [47], [48], our ECS(S) protocol in Figure 13 has computational complexity \(O(dl)\) and communication complexity \(O(dl)\).

Correctness. Similar to ECSS protocol, we have \(\tilde{v}_k = \pi_k^{-1}(v_k^*)\). Therefore, the final sum is computed correctly: \[\begin{align} o_s+o_r &= \sum_{k\in[d]} (\langle \mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k},\mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k} \rangle+\langle \mathbf{x}_k,\mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k} \rangle +\langle \mathbf{y}_k,\mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k} \rangle +z_k-h_k-\mathsf{mask}_k^2)\\ &= \sum_{k\in[d]} (\langle \mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k},\mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k} \rangle+\langle \tilde{\mathbf{a}}_{k,\tilde{v}_k}^0+\mathsf{\mathbf{mask}}_k^0,\mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k} \rangle +\langle \mathbf{b}_{k,\tilde{v}_k}^{\mathcal{S},1}+\mathsf{\mathbf{mask}}_k^1,\mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k} \rangle \\ &+\langle \tilde{\mathbf{a}}_{k,\tilde{v}_k}^0, \mathbf{b}_{k,\tilde{v}_k}^{\mathcal{S},1} \rangle+\mathsf{mask}_k^2-\langle \mathbf{mask}_k^0||\mathbf{mask}_k^1, \mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k}||\mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k} \rangle-\mathsf{mask}_k^2)\\ &= \sum_{k\in[d]} (\langle \mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k},\mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k} \rangle+\langle \tilde{\mathbf{a}}_{k,\tilde{v}_k}^0,\mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k} \rangle +\langle \mathbf{b}_{k,\tilde{v}_k}^{\mathcal{S},1},\mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k} \rangle +\langle \tilde{\mathbf{a}}_{k,\tilde{v}_k}^0, \mathbf{b}_{k,\tilde{v}_k}^{\mathcal{S},1} \rangle)\\ &= \sum_{k \in [d]} (\langle \mathbf{b}^{\mathcal{R},0}_{k,\tilde{v}_k} + \tilde{\mathbf{a}}_{k,\tilde{v}_k}^0,\mathbf{b}^{\mathcal{R},1}_{k,\tilde{v}_k} + \mathbf{b}_{k,\tilde{v}_k}^{\mathcal{S},1} \rangle) \\ &= \sum_{k \in [d]} (\langle \mathbf{b}^{0}_{k,\pi_k(\tilde{v}_k)} + \mathbf{a}_{k,\pi_k(\tilde{v}_k)}^0,\mathbf{b}^{1}_{k,\pi_k(\tilde{v}_k)} \rangle) \\ &= \sum_{k \in [d]} (\langle \mathbf{b}^{0}_{k,v_k^*} + \mathbf{a}_{k,v_k^*}^0,\mathbf{b}^{1}_{k,v_k^*} \rangle) \end{align}\]

Complexity. When using state-of-the-art PS [36] and ssPEQT [47], [48], our ECIPS protocol in Figure 13 has computation complexity \(O(dpl)\) and communication complexity \(O(dpl)\).

Correctness. For \(u\in[m_c]\), if \(\exists \mathbf{w}_i\in W\), s.t. \(\mathsf{dist}(Q^*[\pi(u)],\mathbf{w}_i)\leq \delta\), then the correctness of spatial hashing ensures \(\exists t\in[2^d]\), s.t. \(\mathsf{cell}_\delta(Q^*[\pi(u)]) = \mathcal{C}_{i,t}\), thus \(\forall k\in[d], \mathsf{cell}_\delta(Q^*[\pi(u)])||k||\alpha_{\pi(u)} = \mathcal{C}_{i,t}||k||\alpha_{\pi(u)}\) and \(|Q^*[\pi(u)]_k-w_{i,k}|\leq \delta\). By the property of prefix and the correctness of OPPRF, \(\exists !v\in[l]\), s.t. \(r^\mathcal{S}_{\pi(u),k,v}=r^\mathcal{R}_{\pi(u),k}\). The correctness of ECS guarantees \(\mathsf{Rand}^{\mathcal{S}}_{\pi(u)} = \mathsf{Rand}^{\mathcal{R}}_{\pi(u)}\). Then, the correctness of ssPEQT and PS ensures \(\tilde{b}_{\pi(u)}^\mathcal{S}\oplus \tilde{b}_{\pi(u)}^\mathcal{R}=1\) and \(b_u^{\mathcal{S}}\oplus \bar{b}_u^{\mathcal{R}}=1\). Finally, the correctness of OT ensures the receiver learns \({Q}^*[\pi(u)]\) if \(b_u^{\mathcal{S}}\oplus \bar{b}_u^{\mathcal{R}}=1\). If \(\forall i\in [n], \mathsf{dist}({Q}^*[\pi(u)],\mathbf{w}_i)> \delta\), we have \(\exists k\in[d]\), s.t. \(\forall v\in[l], q_{\pi(u),k,v}^*\notin \{w_{i,k,v'}\}_{v'\in [l']}\). Therefore, the pseudorandomness of PRF in OPPRF guarantees \(r^\mathcal{S}_{\pi(u),k,v}\) is pseudorandom. By setting \(\mathsf{len}= \log |\mathbb{F}|= \lambda +\log mn +\log l\), a union bound shows the probability of \(\exists i\in [n], u\in[m_c], v\in [l], r^\mathcal{S}_{\pi(u),k,v}=r^\mathcal{R}_{\pi(u),k}\) is negligible \(2^{-\lambda}\). By the correctness of ECS, \(\mathsf{Rand}^{\mathcal{S}}_{\pi(u)}\) is also pseudorandom. As a result, \(\mathsf{Rand}^{\mathcal{S}}_{\pi(u)}\ne \mathsf{Rand}^{\mathcal{R}}_{\pi(u)}\) with overwhelming probability and \(\mathcal{R}\) learns \(\perp\) in the final OT.

FPSI variants. The FPSI protocol described in Figure 19 can be easily adapted to support several FPSI variants with only minor adjustments. For LFPSI, the sender simply replaces \(Q^*[\pi(u)]\) with the corresponding label in the final OT step. For FPSI-CA, the sender sends \(b_u^\mathcal{S}\) to the receiver in Step 9, allowing the receiver to compute \(b_u := b_u^\mathcal{S} \oplus \bar{b}_u^{\mathcal{R}}\) and output the Hamming weight of \(\mathbf{b}= (b_1, \dots, b_{m_c})\). For FPSI-SP, the roles are effectively reversed: the receiver sends \(\bar{b}_u^{\mathcal{R}}\) to the sender, who then outputs the set \(\{ Q^*[\pi(u)] : b_u^\mathcal{S} \oplus \bar{b}_u^{\mathcal{R}} = 1,u\in[m_c] \}\). In this case, the sender functionally acts as the receiver in the FPSI-SP definition.

Trade-off from the execution order of PS and PEQT. In our protocol shown in Figure 19, the parties currently use ssPEQT in step 7 to test whether \(\mathsf{Rand}^{\mathcal{S}}_u\) and \(\mathsf{Rand}^{\mathcal{R}}_u\) are equal, then apply PS to the indicator bits in step 8. These two steps can be swapped—the parties may first permute \(\mathsf{Rand}^{\mathcal{R}}_u\) and then test equality between the permuted result using standard PEQT. This reordering improves computational efficiency by replacing ssPEQT with PEQT, but at the expense of communication, since PS would then operate on \(O(\lambda)\)-bit strings rather than single bits.

Optimization from AND. Since testing the \(L_\infty\) distance can be decomposed into independent interval tests for each dimension, we can simplify the protocol as follows. Instead of invoking the ECS protocol, the parties perform ssPEQT on \(r_{u,k,v}^\mathcal{S}\) and \(r_{u,k}^\mathcal{R}\) for each dimension, then XOR the results across all prefixes per dimension. The resulting outputs are combined across dimensions using an AND protocol to produce a secret sharing of the fuzzy matching indication bit. This approach is both simpler and more efficient than the ECS-based construction. The formal description is provided in Figure 20.

Correctness. For \(u\in[m_c]\), if \(\exists \mathbf{w}_i\in W\), s.t. \(\mathsf{dist}(Q^*[\pi(u)],\mathbf{w}_i)\leq \delta\), then the correctness of spatial hashing ensures \(\exists t\in[2^d]\), s.t. \(\mathsf{cell}_\delta(Q^*[\pi(u)]) = \mathcal{C}_{i,t}\), thus \(\forall k\in[d], \mathsf{cell}_\delta(Q^*[\pi(u)])||k||\alpha_{\pi(u)} = \mathcal{C}_{i,t}||k||\alpha_{\pi(u)}\) and \(|Q^*[\pi(u)]_k-w_{i,k}|\leq \delta\). By the property of prefix and the correctness of OPPRF, \(\exists !v\in[l]\), s.t. \(r^\mathcal{S}_{\pi(u),k,v}=r^\mathcal{R}_{\pi(u),k}\). Therefore, \(\forall k\in [d], \exists! v\in[l]\), s.t. \(b_{\pi(u),k,v}^\mathcal{S}\oplus b_{\pi(u),k,v}^\mathcal{R}=1\) and \(b_{\pi(u),k}^\mathcal{S} \oplus b_{\pi(u),k}^\mathcal{R}=1\). By the correctness of AND, \(\tilde{b}^{\mathcal{S}}_{\pi(u)}\oplus \tilde{b}^{\mathcal{R}}_{\pi(u)}=1\). Same as Figure 19, the receiver learns \({Q}^*[\pi(u)]\) if \(b_u^{\mathcal{S}}\oplus \bar{b}_u^{\mathcal{R}}=1\). If \(\forall i\in [n], \mathsf{dist}({Q}^*[\pi(u)],\mathbf{w}_i)> \delta\), we have \(\exists k\in[d]\), s.t. \(\forall v\in[l], q_{\pi(u),k,v}^*\notin \{w_{i,k,v'}\}_{v'\in [l']}\). Therefore, the pseudorandomness of PRF in OPPRF guarantees \(r^\mathcal{S}_{\pi(u),k,v}\) is pseudorandom. By setting \(\mathsf{len}= \log |\mathbb{F}|= \lambda +\log mn +\log l\), a union bound shows the probability of \(\exists i\in [n], u\in[m_c], v\in [l], r^\mathcal{S}_{\pi(u),k,v}=r^\mathcal{R}_{\pi(u),k}\) is negligible \(2^{-\lambda}\). By the correctness of ssPEQT and AND, \(\forall v\in[l], b_{\pi(u),k,v}^\mathcal{S}\oplus b_{\pi(u),k,v}^\mathcal{R}=0\) and \(\tilde{b}_{\pi(u)}^\mathcal{S}\oplus \tilde{b}_{\pi(u)}^\mathcal{R}=0\). As a result, \(\mathcal{R}\) learns \(\perp\) in the final OT.

Correctness. For \(j\in[m]\), if \(\exists \mathbf{w}_i\in W\), s.t. \(\mathsf{dist}(Q^*[\tau(j)],\mathbf{w}_i)\leq \delta\), then the correctness of spatial hashing ensures \(\exists t\in[2^d]\), s.t. \(\mathsf{cell}_\delta(Q^*[\tau(j)]) = \mathcal{C}_{i,t}\), thus \(\forall k\in[d], \mathsf{cell}_\delta(Q^*[\tau(j)])||k||\alpha_{\tau(j)} = \mathcal{C}_{i,t}||k||\alpha_{\tau(j)}\) and \(|Q^*[\tau(j)]_k-w_{i,k}|\leq \delta\). By the property of prefix and the correctness of sOPRF and OKVS, \(\exists !v\in[l]\), s.t. \(r^\mathcal{S}_{j,k,v}=f^1_{j,k,v}\). The correctness of ECSS guarantees \(\mathsf{Rand}^{\mathcal{S}}_{j} + \mathsf{Rand}^{\mathcal{R}}_{j}=r^\mathcal{S}_{j,k,v}-f^1_{j,k,v}=0\). Then, the correctness of PEQT ensures \(b_j=1\). Finally, the correctness of OT ensures the receiver learns \({Q}^*[\tau(j)]\). If \(\forall i\in [n], \mathsf{dist}({Q}^*[\tau(j)],\mathbf{w}_i)> \delta\), we have \(\exists k\in[d]\), s.t. \(\forall v\in[l], q_{\tau(j),k,v}^*\notin \{w_{i,k,v'}\}_{v'\in [l']}\). Therefore, the randomness of OKVS guarantees \(r^\mathcal{S}_{j,k,v}\) is random. By setting \(\mathsf{len}= \log |\mathbb{F}|= \lambda +\log mn +\log l\), a union bound shows the probability of \(\exists i\in [n], u\in[m_c], v\in [l], r^\mathcal{S}_{j,k,v}-f^1_{j,k,v}=0\) is negligible \(2^{-\lambda}\). By the correctness of ECS, \(\mathsf{Rand}^{\mathcal{S}}_{j}\) is also pseudorandom. As a result, \(\mathsf{Rand}^{\mathcal{S}}_{j}\ne \mathsf{Rand}^{\mathcal{R}}_{j}\) with overwhelming probability. \(\mathcal{R}\) receives \(b_j=0\) and learns \(\perp\) in the final OT.

FPSI variants. Similar to the OPPRF-based construction, our sOPRF-based FPSI protocol (Figure 21) can also be adapted to other FPSI variants with minimal modifications. For LFPSI, the sender replaces \(Q^*[\tau(u)]\) with the corresponding label in the final OT step. For FPSI-CA, the receiver directly outputs the Hamming weight of \(\vec{b} = (b_1, \dots, b_{m})\). For FPSI-SP, the roles are effectively reversed: the sender acts as the receiver in the PEQT step (step 8) to learn each \(b_j\), and then outputs the set \({ Q^*[\tau(j)] : b_j = 1, j \in [m] }\). In this case, the sender functionally acts as the receiver in the FPSI-SP definition.

Optimization from AND. Similar to the OPPRF-based construction, our sOPRF-based FPSI protocol (Figure 21) can also be optimized using AND functionality. The formal description is given in Figure 22.

Correctness. For \(j\in[m]\), if \(\exists \mathbf{w}_i\in W\), s.t. \(\mathsf{dist}(Q^*[\tau(j)],\mathbf{w}_i)\leq \delta\), then the correctness of spatial hashing ensures \(\exists t\in[2^d]\), s.t. \(\mathsf{cell}_\delta(Q^*[\tau(j)]) = \mathcal{C}_{i,t}\), thus \(\forall k\in[d], \mathsf{cell}_\delta(Q^*[\tau(j)])||k||\alpha_{\tau(j)} = \mathcal{C}_{i,t}||k||\alpha_{\tau(j)}\) and \(|Q^*[\tau(j)]_k-w_{i,k}|\leq \delta\). By the property of prefix and the correctness of sOPRF and OKVS, \(\exists !v\in[l]\), s.t. \(r^\mathcal{S}_{j,k,v}=f^1_{j,k,v}\). Therefore, \(\forall k\in [d], \exists! v\in[l]\), s.t. \(b_{j,k,v}^\mathcal{S}\oplus b_{j,k,v}^\mathcal{R}=1\) and \(b_{j,k}^\mathcal{S} \oplus b_{j,k}^\mathcal{R}=1\). By the correctness of AND, \(\tilde{b}^{\mathcal{S}}_{j}\oplus \tilde{b}^{\mathcal{R}}_{j}=1\). Same as Figure 19, the receiver learns \({Q}^*[\tau(j)]\) if \(b_j^{\mathcal{S}}\oplus \bar{b}_j^{\mathcal{R}}=1\). If \(\forall i\in [n], \mathsf{dist}({Q}^*[\tau(j)],\mathbf{w}_i)> \delta\), we have \(\exists k\in[d]\), s.t. \(\forall v\in[l], q_{\tau(j),k,v}^*\notin \{w_{i,k,v'}\}_{v'\in [l']}\). Therefore, the randomness of OKVS guarantees \(r^\mathcal{S}_{j,k,v}\) is random. By setting \(\mathsf{len}= \log |\mathbb{F}|= \lambda +\log mn +\log l\), a union bound shows the probability of \(\exists i\in [n], u\in[m_c], v\in [l], r^\mathcal{S}_{j,k,v}-f^1_{j,k,v}=0\) is negligible \(2^{-\lambda}\). By the correctness of ssPEQT and AND, \(\forall v\in[l], b_{j,k,v}^\mathcal{S}\oplus b_{j,k,v}^\mathcal{R}=0\) and \(\tilde{b}_{j}^\mathcal{S}\oplus \tilde{b}_{j}^\mathcal{R}=0\). As a result, \(\mathcal{R}\) learns \(\perp\) in the final OT.

Correctness. For \(u\in[m_c]\), if \(\exists \mathbf{w}_i\in W\), s.t. \(\mathsf{dist}(Q^*[\pi(u)],\mathbf{w}_i)\leq \delta\), then the correctness of spatial hashing ensures \(\exists t\in[2^d]\), s.t. \(\mathsf{cell}_\delta(Q^*[\pi(u)]) = \mathcal{C}_{i,t}\), thus \(\forall k\in[d], \mathsf{cell}_\delta(Q^*[\pi(u)])||\sigma||k||\alpha_{\pi(u)} = \mathcal{C}_{i,t}||\sigma||k||\alpha_{\pi(u)}\) and \(|Q^*[\pi(u)]_k-w_{i,k}|\leq \delta\). By the property of prefix, \(\exists !v\in[l],v'\in [l'],\sigma\in\{0,1\}\), s.t. \(q_{\pi(u),k,v}^*=w_{i,\sigma,k,v'}^*\). By the correctness of OPPRF, we have \(\forall \gamma\in[p], r^{\mathcal{S}}_{\pi(u),\sigma,k,v,\gamma}=r^{\mathcal{R}}_{\pi(u),k,\gamma}+|w_{i,k} -\mathsf{Bound}(\sigma,w_{i,\sigma,k,v'})|^\gamma\) and \(r^{\mathcal{S}}_{\pi(u),\sigma,k,v,p+1}=r^{\mathcal{R}}_{\pi(u),k,p+1}\). Then, the correctness of ECIPS guarantees \[\begin{align} \mathsf{Rand}^{\mathcal{S}}_{\pi(u)}+\mathsf{Rand}^{\mathcal{R}}_{\pi(u)} &= \sum_{k\in[d]}\langle \mathbf{a}^0_{\pi(u),\sigma,k,v}+ \mathbf{b}^0_{\pi(u),\sigma,k,v}, \mathbf{b}^1_{\pi(u),\sigma,k,v} \rangle \\ &= \sum_{k\in[d]}\sum_{\gamma\in[0,p]} \binom{p}{\gamma}|w_{i,k} - \mathsf{Bound}(\sigma,w_{i,\sigma,k,v'}^*)|^\gamma \cdot |Q^*[\pi(u)]_k-\mathsf{Bound}(\sigma,q_{\pi(u),k,v}^*)|^{p-\gamma}\\ &=\sum_{k\in[d]} |w_{i,k}-Q^*[\pi(u)]_k|^p\\ &=\mathsf{dist}(\mathbf{w}_{i},Q^*[\pi(u)])^p \end{align}\] By the correctness of ssIFmat, \(\tilde{b}^\mathcal{S}_{\pi(u)}\oplus \tilde{b}_{\pi(u)}^\mathcal{R}=1\) iff \(\mathsf{Rand}^{\mathcal{S}}_{\pi(u)}\in [-\mathsf{Rand}^{\mathcal{R}}_{\pi(u)} ,-\mathsf{Rand}^{\mathcal{R}}_{\pi(u)}+\delta^p]\), which means \(\mathsf{dist}(\mathbf{w}_{i},Q^*[\pi(u)])^p\in [0,\delta^p]\). Then, the correctness of ssPEQT and PS ensures \(\tilde{b}_{\pi(u)}^\mathcal{S}\oplus \tilde{b}_{\pi(u)}^\mathcal{R}=1\) and \(b_u^{\mathcal{S}}\oplus \bar{b}_u^{\mathcal{R}}=1\). Finally, the correctness of OT ensures the receiver learns \({Q}^*[\pi(u)]\) if \(b_u^{\mathcal{S}}\oplus \bar{b}_u^{\mathcal{R}}=1\). If \(\forall i\in [n], \mathsf{dist}({Q}^*[\pi(u)],\mathbf{w}_i)> \delta\), we have \(\exists k\in[d]\), s.t. \(\forall v\in[l], q_{\pi(u),k,v}^*\notin \{w_{i,k,v'}\}_{v'\in [l']}\). Therefore, the pseudorandomness of PRF in OPPRF guarantees \(r^\mathcal{S}_{\pi(u),k,v}\) is pseudorandom, resulting in \(\mathbf{b}_{\pi(u),\sigma,k,v}^0\) being also pseudorandom (except the first component). The correctness of ECIPS guarantees \(\mathsf{Rand}^{\mathcal{S}}_{\pi(u)}+\mathsf{Rand}^{\mathcal{R}}_{\pi(u)}\) is also pseudorandom. By setting \(\mathsf{len}= \log |\mathbb{F}|= \lambda +\log mn +\log l+p\log \delta\), a union bound shows the probability of \(\exists i\in [n], u\in[m_c], v\in [l], \mathsf{Rand}^{\mathcal{S}}_{\pi(u)}+\mathsf{Rand}^{\mathcal{R}}_{\pi(u)}\in [0,\delta^p]\) is negligible \(2^{-\lambda}\). As a result, \(b_u^{\mathcal{S}}\oplus \bar{b}_u^{\mathcal{R}}=0\) with overwhelming probability. \(\mathcal{R}\) learns \(\perp\) in the final OT.

FPSI variants. The protocol presented in Figure 23 can be similarly extended to support other FPSI variants with straightforward modifications. These adaptations follow exactly the same adjustments as described for the \(L_\infty\) protocol in Figure 19, and we omit them here.

Trade-off from the execution order of PS and IFmat. Similar to the \(L_\infty\) protocol in Figure 19, we can also achieve a trade-off between computation and communication by adjusting the order of (ss)IFmat and PS protocols.

FPSI variants. The protocol presented in Figure 24 can be similarly extended to support other FPSI variants with straightforward modifications. These adaptations follow exactly the same adjustments as described for the \(L_\infty\) protocol in Figure 21, and we omit them here.

Correctness. For \(j\in[m]\), if \(\exists \mathbf{w}_i\in W\), s.t. \(\mathsf{dist}(Q^*[\tau(j)],\mathbf{w}_i)\leq \delta\), then the correctness of spatial hashing ensures \(\exists t\in[2^d]\), s.t. \(\mathsf{cell}_\delta(Q^*[\tau(j)]) = \mathcal{C}_{i,t}\), thus \(\forall k\in[d], \mathsf{cell}_\delta(Q^*[\tau(j)])||\sigma||k||\alpha_{\tau(j)} = \mathcal{C}_{i,t}||\sigma||k||\alpha_{\pi(u)}\) and \(|Q^*[\tau(j)]_k-w_{i,k}|\leq \delta\). By the property of prefix, \(\exists !v\in[l],v'\in [l'],\sigma\in\{0,1\}\), s.t. \(q_{\pi(u),k,v}^*=w_{i,\sigma,k,v'}^*\). By the correctness of sOPRF and OKVS, we have \(\forall \gamma\in[p], r^{\mathcal{S}}_{j,\sigma,k,v,\gamma}=f^{1}_{j,\sigma,k,v,\gamma}+|w_{i,k} -\mathsf{Bound}(\sigma,w_{i,\sigma,k,v'})|^\gamma\) and \(r^{\mathcal{S}}_{j,\sigma,k,v,p+1}=f^{1}_{j,\sigma,k,v,p+1}\). Then, the correctness of ECIPS guarantees \[\begin{align} \mathsf{Rand}^{\mathcal{S}}_{j}+\mathsf{Rand}^{\mathcal{R}}_{j} &= \sum_{k\in[d]}\langle \mathbf{a}^0_{j,\sigma,k,v}+ \mathbf{b}^0_{j,\sigma,k,v}, \mathbf{b}^1_{j,\sigma,k,v} \rangle \\ &= \sum_{k\in[d]}\sum_{\gamma\in[0,p]} \binom{p}{\gamma}|w_{i,k} - \mathsf{Bound}(\sigma,w_{i,\sigma,k,v'}^*)|^\gamma \cdot |Q^*[\tau(j)]_k-\mathsf{Bound}(\sigma,q_{\tau(j),k,v}^*)|^{p-\gamma}\\ &=\sum_{k\in[d]} |w_{i,k}-Q^*[\tau(j)]_k|^p\\ &=\mathsf{dist}(\mathbf{w}_{i},Q^*[\tau(j)])^p \end{align}\] By the correctness of IFmat, \(b_j=1\) iff \(\mathsf{Rand}^{\mathcal{S}}_{j}\in [-\mathsf{Rand}^{\mathcal{R}}_{j} ,-\mathsf{Rand}^{\mathcal{R}}_{j}+\delta^p]\), which means \(\mathsf{dist}(\mathbf{w}_{i},Q^*[\tau(j)])^p\in [0,\delta^p]\). Finally, the correctness of OT ensures the receiver learns \({Q}^*[\tau(j)]\). If \(\forall i\in [n], \mathsf{dist}({Q}^*[\tau(j)],\mathbf{w}_i)> \delta\), we have \(\exists k\in[d]\), s.t. \(\forall v\in[l], q_{\tau(j),k,v}^*\notin \{w_{i,k,v'}\}_{v'\in [l']}\). Therefore, the randomness of OKVS guarantees \(\mathbf{r}^\mathcal{S}_{j,\sigma,k,v}\) is random, resulting in \(\mathbf{b}_{j,\sigma,k,v}^0\) is also pseudorandom (except the first component). The correctness of ECIPS guarantees \(\mathsf{Rand}^{\mathcal{S}}_{j}+\mathsf{Rand}^{\mathcal{R}}_{j}\) is also random. By setting \(\mathsf{len}= \log |\mathbb{F}|= \lambda +\log mn +\log l+p\log \delta\), a union bound shows the probability of \(\exists i\in [n], j\in[m], v\in [l], \mathsf{Rand}^{\mathcal{S}}_{j}+\mathsf{Rand}^{\mathcal{R}}_{j}\in [0,\delta^p]\) is negligible \(2^{-\lambda}\). As a result, \(\mathcal{R}\) receives \(b_j=0\) in IFmat and learns \(\perp\) in the final OT.

Correctness. If \(\exists \mathbf{q}_j\in Q, \mathbf{w}_i\in W\), s.t. \(\mathsf{dist}(\mathbf{q}_j,\mathbf{w}_i)\leq \delta\), we have \(\forall k\in[d], q_{j,k} \in [w_{i,k}-\delta,w_{i,k}+\delta]\). By the property of prefix, we have \(\forall k\in[d], \exists ! v\in [l],v'\in[l'], q_{j,k,v}^* = w_{i,k,v'}^*\) Then, from the definition of \(B\), we have \(B[k||q_{j,k,v}^*]=B[k||w_{i,k,v'}^*] = B[k||w_{i,k,1}^*],k\in[d]\). By the correctness of sOPRF and OKVS, we have \(r_{\mathcal{S},j,k,v,0} = B[k||w_{i,k,v'}^*]+f_{\mathcal{S},j,k,v,0}^1\) and \(r_{\mathcal{S},j,k,v,1} =f_{\mathcal{S},j,k,v,1}^1\). By the correctness of ECSS, we have \(\sigma_{\mathcal{S},j}'+\sigma_{\mathcal{S},j}^1= \sum_{k\in[d]} (r_{\mathcal{S},j,k,v,0} -f_{\mathcal{S},j,k,v,0}^1 )=\sum_{k\in[d]} B[k||w_{i,k,v'}^*]=\mathsf{pid}^{\mathcal{R}}_i\). By the correctness of final two sOPRF, we have \(id_{\mathbf{q}_j} = F_{sk_{\mathcal{R}}'}(F_{sk_{\mathcal{S}}'}( \mathsf{pid}^{\mathcal{R}}_i+\mathsf{pid}^{\mathcal{S}}_j ))\). Symmetrically, we also have \(id_{\mathbf{w}_i} = F_{sk_{\mathcal{R}}'}(F_{sk_{\mathcal{S}}'}( \mathsf{pid}^{\mathcal{R}}_i+ \mathsf{pid}^{\mathcal{S}}_j)) = id_{\mathbf{q}_j}\).

Distinctiveness. For any \(i \in [n]\), the \(d\)-separate set assumption guarantees the existence of a \(k_i \in [d]\) such that the interval \([w_{i,k_i} - \delta, w_{i,k_i} + \delta]\) does not overlap with any other interval \([w_{i',k_i} - \delta, w_{i',k_i} + \delta]\) for \(i' \neq i\). By the property of prefix, we have \(\forall i,i'\in[n], \{w_{i,k_i,v}^*\}_{v\in [l']}\cap \{w_{i',k_{i'},v}^*\}_{v\in [l']}=\emptyset\). Consequently, a unique and uniform random value \(\mathsf{Rand}^{\mathcal{R}}_{i,k_i}\) is added to \(\mathsf{pid}^{\mathcal{R}}_{i}\), ensuring that \(\mathsf{pid}^{\mathcal{R}}_{i}\) is independent of \(\mathsf{pid}^{\mathcal{R}}_{i'}\) for all \(i' \neq i\). By setting \(|\mathbb{F}| \geq \lambda + \log n\), the union bound demonstrates that the probability of \(\exists i' \neq i\) such that \(\mathsf{pid}^{\mathcal{R}}_{i'} = \mathsf{pid}^{\mathcal{R}}_i\) is negligible \(2^{-\lambda}\). Since \(\mathsf{ID}_{\mathbf{w}_i} = F_{sk_{\mathcal{R}}'}(F_{sk_{\mathcal{S}}'}( \mathsf{pid}^{\mathcal{R}}_i+\Delta_i ))\), where \(\Delta_i\) is the remaining addend, it follows that the probability of \(\exists i' \neq i\) such that \(\mathsf{ID}_{\mathbf{w}_{i'}} = \mathsf{ID}_{\mathbf{w}_i}\) is also negligible \(2^{-\lambda}\).

Randomness. The randomness can be easily obtained by combining the distinctiveness and the pseudorandomness of PRFs.

Comparison in Low Dimension. As shown in Table 1, we observed that, for \(d\in\{3,4\}\), [30]-Low’s data shows non-monotonic scaling with \(\delta\), with costs dropping unexpectedly at \(\delta=64\) (marked in red), suggesting potential implementation issues. Nevertheless, our protocols exhibit significant performance improvements in almost all parameters. For instance, with \(n=m=2^{12}\), \(d=4\), and \(\delta=256\), our \(\Pi_{\mathsf{SA}}^{\mathsf{apart}}\) achieves up to \(18\times\) speedup and \(21.6\times\) lower communication overhead. While \(\Pi_{\mathsf{SA}}^{\mathsf{apart}}\) performs best at smaller set sizes (\(n=2^8\)), \(\Pi_{\mathsf{OA}}^{\mathsf{apart}}\) scales more favorably as the set size increases, owing to the higher efficiency of the OPRF protocol within OPPRF under large parameter settings.

Comparison in High Dimension. As shown in Table 2, our protocols maintain substantial advantages in high-dimensional settings. For example, with \(m=n=2^8\), \(d=4\), and \(\delta=256\), our \(\Pi_{\mathsf{SA}}^{\mathsf{apart}}\) achieves up to \(43.7\times\) speedup and \(28.4\times\) lower communication overhead. Notably, both [22] and [30]-High encountered memory overflow at \(m=n=2^{16}\), whereas our protocols execute successfully under the same configuration.

Security Flaw. The primary security flaw in their protocol occurs in step 5. Here, each value \(u_{k,v}\) is derived from the sender’s element as \(u_{k,v} = \mathsf{Decode}(E, q_{k,v}^*)\). To ensure security, each \(u_{k,v}\) must be masked with an independent random value, analogous to a one-time pad encryption. However, the protocol reuses a single random value \(a_k\) to mask all \(\{u_{k,v}\}_{v \in [l]}\) within the same dimension. This reuse is equivalent to key reuse in a one-time pad and therefore compromises the protocol’s security.

A Concrete Attack. We present a concrete attack. In step 6, the receiver obtains all ciphertexts \(\{u^*_{k,v}\}_{k\in[d],v\in[l']}\). Decrypting each yields \[m_{k,v} := \mathsf{Dec}_{sk}(u_{k,v}^*) = \mathsf{Dec}_{sk}\bigl(\mathsf{Decode}(E, H_{\gamma_1}(k||q_{k,v}^*))\bigr) + a_k .\] Since the same mask \(a_k\) is reused across all \(v\in[l']\), the receiver can eliminate \(a_k\) by computing differences between the \(m_{k,v}\), even without knowing \(a_k\). For instance, \[\Delta_1 := m_{k,2} - m_{k,1} = \mathsf{Dec}_{sk}\bigl(\mathsf{Decode}(E, H_{\gamma_1}(q_{k,2}^*))\bigr) - \mathsf{Dec}_{sk}\bigl(\mathsf{Decode}(E, H_{\gamma_1}(q_{k,1}^*))\bigr).\] Now \(\Delta_1\) depends only on the sender’s element \(\mathbf{q}\), not on \(a_k\). The receiver can then guess candidate values for \(q_{k,1}^*\) and \(q_{k,2}^*\), compute the corresponding right-hand side of the above equation, and check whether it matches \(\Delta_1\). A successful match reveals information about the sender’s private input \(\mathbf{q}\).

Proof Flaw. We then examine where their security proof breaks down. In their introduction, they assert that security holds because “only one value in \(\{u_{k,v} \boxplus a_k\}_{v \in [l]}\) encrypts \(a_k\) for each \(k\), while others encrypt random values.”

For instance, in the case where the receiver’s output is \(0\), their proof (Theorem 4) simulates each ciphertext \(u^*_{k,v}\) as a random ciphertext (see Step \(3'\) of the simulator in Security against a Corrupted Receiver). They argue that due to the randomness of the OKVS, \(u^*_{k,v}\) is indistinguishable from a random ciphertext (cf. hybrids \(\mathcal{H}_0\)–\(\mathcal{H}'_0\) in the same proof).

This reasoning misapplies the randomness property of OKVS. The formal randomness guarantee of an OKVS states that if a key is not in the encoded set, the decoded value appears random to any party that does not know the OKVS encoding \(E\) (see Section 2.9 for the formal definition). In their protocol, however, the receiver itself generates \(E\) and thus knows it completely. Consequently, from the receiver’s perspective, no randomness remains in the decoding result \(u^*_{k,v}\)—the receiver can directly check whether a query \(q\) satisfies \(u^* = \mathsf{Decode}(E, H(q))\).

The situation parallels that of a Pseudo-Random Function (PRF). A function family is a PRF if an adversary with oracle access cannot distinguish it from a truly random function, provided the adversary does not know the PRF key. If the key is revealed, the adversary trivially distinguishes the two. Here the OKVS encoding \(E\) plays the role of the key; once it is known to the receiver, the randomness condition no longer applies. Hence, their security proof is invalid on this point.

Security Flaws. Their dIDG protocol suffers from two security flaws. The first, already discussed in Section 8.1, arises from the sender’s reuse of a single \(\mathsf{mask}_{j,k}\) to mask all \(\{u_{j,k,v}\}_{v\in[l']}\); we do not elaborate on it further here.

A second problem is that the IDs generated by their protocol fail to satisfy the randomness requirement defined for fuzzy mapping (see Section 2.14). In other words, the ID set \(\{id_{\mathbf{q}_j}\}_{j\in[m]}\) depends on the receiver’s set \(W\), thereby leaking additional information about receiver’s set. The lack of randomness stems from the fact that their ID definition incorporates only randomness contributed by the receiver, while the receiver’s OKVS encoding may assign identical random values to overlapping intervals (see step 3). This can lead to collisions of the form \(\exists j_1 \neq j_2\) such that \(id_{\mathbf{q}_{j_1}} = id_{\mathbf{q}_{j_2}}\), which reveals to the sender that some receiver’s element lies near either \(\mathbf{q}_{j_1}\) or \(\mathbf{q}_{j_2}\).

A Concrete Attack. We present a concrete example to illustrate the leakage in their protocol. Let \(m = n = 2\), \(d = 2\), \(\delta = 1\), and suppose the sender holds \(Q = \{\mathbf{q}_1 = (1,0), \mathbf{q}_2 = (1,3)\}\) while the receiver holds \(W = \{\mathbf{w}_1 = (1,1), \mathbf{w}_2 = (4,2)\}\). It is straightforward to verify that \(Q\) and \(W\) satisfy the separate assumption.

Following the receiver’s encoding procedure, in the first dimension the projection interval \([0,2]\) of \(\mathbf{w}_1\) is assigned a random value \(\mathsf{Rand}^{\mathcal{R}}_{1,1}\), and the interval \([3,5]\) of \(\mathbf{w}_2\) is assigned \(\mathsf{Rand}^{\mathcal{R}}_{2,1}\). In the second dimension, \(\mathbf{w}_1\)’s interval \([0,2]\) is assigned \(\mathsf{Rand}^{\mathcal{R}}_{1,2}\), and \(\mathbf{w}_2\)’s interval \([1,3]\) is assigned \(\mathsf{Rand}^{\mathcal{R}}_{2,2}\). However, because the intervals \([0,2]\) and \([1,3]\) overlap in the second dimension, the random value associated with \([1,3]\) is reassigned to \(\mathsf{Rand}^{\mathcal{R}}_{1,2}\), meaning the entire combined interval \([0,3]\) is encoded with \(\mathsf{Rand}^{\mathcal{R}}_{1,2}\).

Consequently, the receiver defines the ID of its first element as \(id_{\mathbf{w}_1} = \mathsf{Rand}^{\mathcal{R}}_{1,1} + \mathsf{Rand}^{\mathcal{R}}_{1,2}\) and the ID of its second element as \(id_{\mathbf{w}_2} = \mathsf{Rand}^{\mathcal{R}}_{2,1} + \mathsf{Rand}^{\mathcal{R}}_{1,2}\).

Now consider the sender. Its first element \(\mathbf{q}_1 = (1,0)\) decodes to \(\mathsf{Rand}^{\mathcal{R}}_{1,1}\) in the first dimension and \(\mathsf{Rand}^{\mathcal{R}}_{1,2}\) in the second dimension, yielding \(id_{\mathbf{q}_1} = \mathsf{Rand}^{\mathcal{R}}_{1,1} + \mathsf{Rand}^{\mathcal{R}}_{1,2}\). Its second element \(\mathbf{q}_2 = (1,3)\) also decodes to \(\mathsf{Rand}^{\mathcal{R}}_{1,1}\) and \(\mathsf{Rand}^{\mathcal{R}}_{1,2}\), giving \(id_{\mathbf{q}_2} = \mathsf{Rand}^{\mathcal{R}}_{1,1} + \mathsf{Rand}^{\mathcal{R}}_{1,2} = id_{\mathbf{q}_1}\). Observing that \(id_{\mathbf{q}_1} = id_{\mathbf{q}_2}\), the sender learns that there exists a receiver element within distance \(\delta\) of \(\mathbf{q}_1\) or \(\mathbf{q}_2\). In an FPSI protocol, the sender should obtain no information about the receiver’s set, so this constitutes an unintended information leakage.

Proof Flaw. We then examine where their security proof breaks down. The security proof for their dIDG protocol (Theorem 12) is not itself flawed (apart from the issue described in Section 8.1), because in that proof the simulator is given the actual inputs and outputs of the parties. For instance, when the sender is corrupted, the simulator receives \((Q, \mathsf{ID}_Q)\) and can completely simulate the sender’s view of the protocol.

The actual error lies in the proof of their full FPSI protocol, namely Theorem 14. In that proof, to invoke the dIDG simulator, the authors simulate the identifiers using randomly generated IDs (see step \(2'\) of the simulator under Security for corrupted Sender). This step implicitly assumes that the generated IDs are uniformly random. However, as we have shown, their ID construction does not satisfy this randomness property. Consequently, this assumption invalidates their proof.