Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

Abstract

Previous FPSI works have demonstrated a linear scaling with the distance threshold $\hat{I}´$, while some recent works have achieved a poly-logarithmic dependence on $\hat{I}´$. However, these protocols either support only the $L_{\infty }$ distance, or they support general $L_{p\in [1,\infty ]}$ distances but rely on expensive additive homomorphic encryption (AHE). Achieving exact logarithmic dependence on $\hat{I}´$ for general $L_{p\in [1,\infty ]}$ distances without relying on costly AHE would constitute a theoretical breakthrough in optimal threshold scaling and a practical advance toward scalable FPSI applications. In this work, we present new FPSI protocols for $L_{p\in [1,\infty ]}$ distances that are entirely built from oblivious transfer (OT) and symmetric-key primitives. We propose FPSI protocols based on both the apart and the separate assumptions, which are applicable to low- and high-dimensional settings, respectively. Our constructions achieve strictly logarithmic complexity in $\hat{I}´$, which is optimal in the sense that distinguishing all values in an interval of length $O(\hat{I}´)$ necessarily requires $\hat{I}\text{c◯}(\log \hat{I}´)$ bits of information. Our core idea is to perform fuzzy matching via prefix representation and interactively determine the correct prefix using equality conditions. To this end, we propose a suite of new components that can be implemented efficiently using only OT and symmetric-key operations. We implement our FPSI protocols and compare them with the state-of-the-art FPSI protocols for $L_{p\in [1,\infty ]}$ distance. Experiments show that our protocols outperform the prior state-of-the-art by up to $43.7\times$ in runtime and $31.3\times$ in communication.