Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

Computer Science > Cryptography and Security [Submitted on 12 Aug 2026] Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching Meng Hao, Xinpeng Yang, Hanxiao Chen, Tianwei Zhang, Haiyang Xue, Guomin Yang, Hongwei Li, Robert H. Deng In this paper, we present scalable fuzzy PSI protocols for general L p∈[1,∞] 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(dlogδ) overhead, compared to O((logδ ) d ) in previous works. The second leverages customized oblivious transfer (OT) with O(dℓ) overhead, where ℓ 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δ, 2 d , without the O((logδ ) d ) or O(δ) 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δ but rely on the strong globally disjoint assumption.} Extensive evaluations demonstrate that our protocols achieve up to a 145× speedup in running time and a 20× reduction in communication cost compared to van Baarsen and Pu~(ASIACRYPT'25), and achieve up to a 25× speedup in running time and up to a 17× reduction in communication cost compared to Piske et al.~(CCS'25). Comments: ACM CCS 2026 Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2608.11526 [cs.CR]   (or arXiv:2608.11526v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2608.11526 Focus to learn more Submission history From: Meng Hao [view email] [v1] Wed, 12 Aug 2026 00:30:53 UTC (286 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-08 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?)