Paper 2025/1796

Efficient Fuzzy PSI Based on Prefix Representation

Abstract

Fuzzy PSI is a variant of PSI, which on input a set of points from the receiver and sender respectively, allows the receiver to learn which of the sender's points lie within a threshold distance $\delta$ under a specific distance metric. Baarsen and Pu (EUROCRYPT'24) first proposed efficient fuzzy PSI protocols for general $L_{p}$ distances (where $p \in [1, \infty]$) in $d$-dimensional space, achieving communication complexity linear in the input size, $\delta$, and $2^d d$. However, they leave open the question of whether the prefix technique of Chakraborti et al. (USENIX Security'23) can further reduce the communication complexity of their fuzzy PSI protocols in both low and high dimensions. In this work, we thoroughly explore using the prefix technique to reduce the complexity of fuzzy PSI. First, we propose fuzzy matching protocols for $L_{\infty}$ and $L_p$ distances, where the communication complexity is improved from $O(\delta d)$ to $O(\log\delta\, d)$ for $L_\infty$, and from $O(\delta^p)$ to $O((\log \delta)^d p)$ for $L_p$ distance. By applying our fuzzy matching protocol in conjunction with spatial hashing, we propose fuzzy PSI protocols for low-dimensional space. For high-dimensional space, we present the first fuzzy PSI protocols achieving communication and computation complexity that scales logarithmically in $\delta$ and linearly in dimension $d$ and input set sizes. We implement our fuzzy PSI protocols and compare them with state-of-the-art protocols. Experimental results demonstrate that our protocols achieve superior performance for large $\delta$: for input size $N=2^8$, $d=5$, and $\delta=256$, our protocol requires $10$--$36\times$ less running time and $3$--$4.5\times$ lower communication than existing protocols.