Search papers, labs, and topics across Lattice.
This paper introduces the first efficient fuzzy private set intersection (PSI) protocols for general \( L_{p\in[1,\infty]} \) distances under one-sided assumptions, utilizing only lightweight symmetric-key primitives. By incorporating prefix trie techniques, the authors achieve a significant reduction in overhead, with complexities scaling as \( O(\log\delta) \) compared to previous methods that scaled as \( O((\log\delta)^d) \) or \( O(\delta) \). Extensive experiments demonstrate that these protocols outperform existing constructions, achieving up to 4818 times faster computation and 282 times lower communication in various scenarios.
Achieving up to 4818 times faster computation in fuzzy PSI protocols could revolutionize privacy-preserving data sharing in real-time applications.
Fuzzy private set intersection (PSI) enables two parties to identify approximately matching elements between their input sets, where two elements are considered a match if their distance is at most a threshold $\delta$ under a given metric. Although substantial progress has been made, existing constructions for general Minkowski distances either rely on strong two-sided geometric separation assumptions or incur substantial overhead under one-sided assumptions. In this work, we present the first concretely efficient fuzzy PSI protocols for general $L_{p\in[1,\infty]}$ distances under one-sided assumptions, relying solely on lightweight symmetric-key primitives. Our constructions support both sender-sided and receiver-sided settings. We further study sparser input distributions and present more efficient protocols tailored to this case. To reduce the overhead scaling with $\delta$, we non-trivially incorporate prefix trie techniques into our protocols, achieving $O(\log\delta)$ complexity for general $L_{p\in[1,\infty]}$ distances for the first time, improving upon $O((\log\delta)^d)$ or $O(\delta)$ complexities of prior works. Extensive experiments, across a wide range of parameter settings, show that our protocols significantly outperform prior works under the same assumptions. Specifically, against van Baarsen and Pu (EUROCRYPT'24), our protocols achieve up to $239\times$ faster computation and up to $20\times$ lower communication. Against Dang et al. (CCS'25), we achieve up to $518\times$ speedup and up to $63\times$ communication reduction. Against Bui et al. (ASIACRYPT'25), we achieve up to $4818\times$ faster computation and up to $282\times$ lower communication.
