Search papers, labs, and topics across Lattice.
This paper introduces efficient Fuzzy Private Set Intersection (FPSI) protocols for $L_{p \in [1, \infty]}$ distance metrics using secret-shared Oblivious Programmable PRFs (OPRF). The protocols achieve linear communication and computation complexity in the set sizes, dimension, and distance threshold, and further incorporate a prefix technique to reduce the dependence on the distance threshold to logarithmic. Empirical evaluations demonstrate significant performance improvements, achieving speedups of up to $145\times$ in running time and reductions of up to $19\times$ in communication cost compared to state-of-the-art FPSI constructions.
Fuzzy Private Set Intersection just got a whole lot faster: new protocols slash runtime by up to 145x and communication costs by 19x compared to existing methods.
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 \cap W$. Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q \in Q$ for which there exists some $w \in W$ satisfying $\mathsf{dist}(q, w) \le \delta$ under a given distance metric. Although several FPSI works are proposed for $L_{p}$ distance metrics with $p \in [1, \infty]$, 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 $L_{p \in [1, \infty]}$ 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 $\delta$. 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 $\delta$ to logarithmic, which is particularly suitable for large $\delta$. 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{\sim}145\times$ in running time and a reduction of $3{\sim}8\times$ in communication cost compared to Gao et al.~(ASIACRYPT'24) and a speedup of $9{\sim}80\times$ in running time and a reduction of $5{\sim}19\times$ in communication cost compared to Dang et al.~(CCS'25).
