International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Fuzzy Private Set Intersection from Fuzzy Mapping

Authors:
Ying Gao , School of Cyber Science and Technology, Beihang University, Beijing, China
Lin Qi , School of Cyber Science and Technology, Beihang University, Beijing, China
Xiang Liu , School of Cyber Science and Technology, Beihang University, Beijing, China
Yuanchao Luo , School of Cyber Science and Technology, Beihang University, Beijing, China
Longxin Wang , School of Cyber Science and Technology, Beihang University, Beijing, China
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2024
Abstract: Private set intersection (PSI) allows Sender holding a set \(X\) and Receiver holding a set \(Y\) to compute only the intersection \(X\cap Y\) for Receiver. We focus on a variant of PSI, called fuzzy PSI (FPSI), where Receiver only gets points in \(X\) that are at a distance not greater than a threshold from some points in \(Y\). Most current FPSI approaches first pick out pairs of points that are potentially close and then determine whether the distance of each selected pair is indeed small enough to yield FPSI result. Their complexity bottlenecks stem from the excessive number of point pairs selected by the first picking process. Regarding this process, we consider a more general notion, called fuzzy mapping (Fmap), which can map each point of two parties to a set of identifiers, with closely located points having a same identifier, which forms the selected point pairs. We initiate the formal study on Fmap and show novel Fmap instances for Hamming and \(L_\infty\) distances to reduce the number of selecte
BibTeX
@inproceedings{asiacrypt-2024-34725,
  title={Efficient Fuzzy Private Set Intersection from Fuzzy Mapping},
  publisher={Springer-Verlag},
  author={Ying Gao and Lin Qi and Xiang Liu and Yuanchao Luo and Longxin Wang},
  year=2024
}