Search papers, labs, and topics across Lattice.
This paper introduces scalable fuzzy private set intersection (PSI) protocols that efficiently handle both low- and high-dimensional data using two innovative fuzzy matching techniques. The first technique employs a role-reversed oblivious PRF, achieving a significant overhead reduction from $O((\log \delta)^d)$ to $O(d\log \delta)$, while the second utilizes customized oblivious transfer with $O(d\ell)$ overhead for short inputs. Experimental results indicate that these protocols can deliver up to a 145x speedup in running time and a 20x reduction in communication costs compared to existing methods, marking a substantial advancement in fuzzy PSI efficiency.
Achieving up to a 145x speedup in fuzzy PSI protocols could redefine the efficiency benchmarks for secure multi-party computations.
In this paper, we present scalable fuzzy PSI protocols for general $L_{p \in [1, \infty]}$ distance, supporting both low- and high-dimensional sets. The core technique is two efficient fuzzy matching protocols. The first is built from a role-reversed oblivious PRF (OPRF) and realizes $O(d\log \delta)$ overhead, compared to $O((\log \delta)^d)$ in previous works. The second leverages customized oblivious transfer (OT) with $O(d\ell)$ overhead, where $\ell$ is the bit length of inputs, which is particularly suitable for short inputs. With these new techniques, we further propose a new dual-layer hashing framework for fuzzy PSI over low-dimensional sets, instantiated with our OT-based fuzzy matching and enhanced with a domain reduction optimization. The protocols achieve an overhead linear with $n, m, \log \delta, 2^d$, without the $O((\log \delta)^d)$ or $O(\delta)$ factors present in prior works. {For high-dimensional sets, we construct fuzzy PSI protocols based on our OPRF- and OT-based fuzzy matching, which achieve an asymptotic overhead linear with $n, m, d$, and $\log \delta$ but rely on the strong globally disjoint assumption.} Extensive evaluations demonstrate that our protocols achieve up to a $145\times$ speedup in running time and a $20\times$ reduction in communication cost compared to van Baarsen and Pu~(ASIACRYPT'25), and achieve up to a $25\times$ speedup in running time and up to a $17\times$ reduction in communication cost compared to Piske et al.~(CCS'25).
