Welcome to the resource topic for 2025/885
Title:
Fast Fuzzy PSI from Symmetric-Key Techniques
Authors: Cong Zhang, Yu Chen, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Anyu Wang, Xiaoyun Wang
Abstract:Private set intersection (PSI) enables a sender holding a set Q and a receiver holding a set W 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 w\in W such that \dist(q, w) \leq \delta with respect to some distance metric. Recently, Gao et al. (ASIACRYPT 2024) proposed the first FPSI protocols for L_\infty and L_{p\in[1,\infty)} distance with linear complexity. They summarized their FPSI construction into two steps: fuzzy mapping and fuzzy matching. However, their realizations of the two steps heavily rely on public key operations, namely the DH-key exchange and additively homomorphic encryption, resulting in low efficiency.
In this work, we propose new FPSI protocols for L_\infty and L_{p\in[1,\infty)} distances, primarily leveraging symmetric-key primitives.
We revisit the definition of fuzzy mapping and rigorously redefine it as a cryptographic scheme. We further introduce consistency for fuzzy mapping scheme, which could simplify the fuzzy matching step into plain PSI.
We then demonstrate how to execute fuzzy mapping step satisfying consistency. We also propose several new technologies to completely avoid the extensive use of computationally expensive public-key operations burden inherent in existing solutions.
We implement our FPSI protocols and compare them with the state-of-the-art FPSI protocols. Experiments show that our protocols perform better than state-of-the-art under all the parameters we tested. Specifically, our protocols achieve a 2.2-83.9 \times speedup in running time and 1.5-11.5 \times shrinking in communication cost, depending on set sizes, dimension and distance threshold.
ePrint: https://eprint.iacr.org/2025/885
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .