Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

Computer Science > Cryptography and Security [Submitted on 16 Apr 2026] Efficient Fuzzy Private Set Intersection from Secret-shared OPRF Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang Private set intersection (PSI) enables a sender holding a set Q of size m and a receiver holding a set W of size n to securely compute the intersection Q \cap W. Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items q \in Q for which there exists some w \in W satisfying \mathsf{dist}(q, w) \le \delta under a given distance metric. Although several FPSI works are proposed for L_{p} distance metrics with p \in [1, \infty], they either heavily rely on expensive homomorphic encryptions, or incur undesirable complexity, e.g., exponential to the element dimension, both of which lead to poor practical efficiency. In this work, we propose efficient FPSI protocols for L_{p \in [1, \infty]} distance metrics, primarily leveraging significantly cheaper symmetric-key operations. Our protocols achieve linear communication and computation complexity in the set sizes m,n, the dimension d, and the distance threshold \delta. Our core building block is an oblivious programmable PRF with secret-shared outputs, which may be of independent interest. Furthermore, we incorporate a prefix technique that reduces the dependence on the distance threshold \delta to logarithmic, which is particularly suitable for large \delta. We implement our FPSI protocols and compare them with state-of-the-art constructions. Experimental results demonstrate that our protocols consistently and significantly outperform existing works across all settings. Specifically, our protocols achieve a speedup of 12{\sim}145\times in running time and a reduction of 3{\sim}8\times in communication cost compared to Gao et al.~(ASIACRYPT'24) and a speedup of 9{\sim}80\times in running time and a reduction of 5{\sim}19\times in communication cost compared to Dang et al.~(CCS'25). Comments: Accepted to the 2026 IEEE Symposium on Security and Privacy (SP) Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2604.14909 [cs.CR]   (or arXiv:2604.14909v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.14909 Focus to learn more Submission history From: Xinpeng Yang [view email] [v1] Thu, 16 Apr 2026 11:51:25 UTC (2,410 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 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?)