Distance-Aware Private Set Intersection

Fuzzy Private Set Intersection (FPSI) is a cryptographic protocol that extends traditional PSI to enable privacy-preserving similarity matching, allowing the receiver to learn elements from the sender’s set with "δ − close" of the receiver’s elements, computing yj | dist(xi, yj) ≤ δ, xi ∈ X, yj ∈ Y where δ is predefined threshold. However, the current state-of-the-art integer-based approach by Chakraborti et al. (USENIX’23) suffers from excessive computation overhead, large communication costs, and limited scalability, hindering practical deployment.We construct two semi-honest $\Pi _{{\text{FPSI}}}^{{\text{int}}}$ for different scenarios. Along with compact Prefix Trie preprocessing, for the balanced settings, we propose $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ leveraging OKVS and subVOLE. For unbalanced scenarios, we introduce $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol combining optimization techniques including Paterson-Stockmeyer algorithms and multiple algorithmic improvements.We implement our protocols in C++ using 32-bit IPv4 and 128-bit IPv6 addresses across balanced and unbalanced scenarios under single-threaded LAN environment. our balanced $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ protocol achieves 24.7-58.4× computational speedup across all scales and 9.9× communication reduction compared to Chakraborti et al. (USENIX'23) for datasets up to 1 million addresses. For unbalanced scenarios, our $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol demonstrates superior scalability, enabling mobile devices with only 4K datasets against 16 million server elements in 56.74 seconds with 22.8 MB communication, achieving 2.8-38.5× speedup over the (USENIX'23).