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

Computer Science > Cryptography and Security [Submitted on 13 Jun 2026] Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang Previous FPSI works have demonstrated a linear scaling with the distance threshold \delta, while some recent works have achieved a poly-logarithmic dependence on \delta. 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 \delta 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 \delta, which is optimal in the sense that distinguishing all values in an interval of length O(\delta) necessarily requires \Omega(\log \delta) 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. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2606.15093 [cs.CR]   (or arXiv:2606.15093v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.15093 Focus to learn more Submission history From: Cong Zhang [view email] [v1] Sat, 13 Jun 2026 03:59:35 UTC (184 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)