Paper 2024/1462

Efficient Fuzzy Private Set Intersection from Fuzzy Mapping

Ying Gao, Beihang University, Beijing, China, Zhongguancun Laboratory, Beijing, China
Lin Qi, Beihang University, Beijing, China
Xiang Liu, Beihang University, Beijing, China
Yuanchao Luo, Beihang University, Beijing, China
Longxin Wang, Beihang University, Beijing, China
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 selected pairs. We demonstrate the powerful capability of Fmap with some superior properties in constructing FPSI variants and provide a generic construction from Fmap to FPSI. Our new Fmap instances lead to the fastest semi-honest secure FPSI protocols in high-dimensional space to date, for both Hamming and general \(L_{\mathsf p\in [1, \infty]}\) distances. For Hamming distance, our protocol is the first one that achieves strict linear complexity with input sizes. For \(L_{\mathsf p\in [1, \infty]}\) distance, our protocol is the first one that achieves linear complexity with input sizes, dimension, and threshold.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2024
Keywords
Fuzzy private set intersectionFuzzy mappingMulti-query fuzzy RPMT
Contact author(s)
gaoying @ buaa edu cn
19373287 @ buaa edu cn
lx1234 @ buaa edu cn
19373507 @ buaa edu cn
wlx_buaa @ buaa edu cn
History
2024-09-22: revised
2024-09-19: received
See all versions
Short URL
https://ia.cr/2024/1462
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1462,
      author = {Ying Gao and Lin Qi and Xiang Liu and Yuanchao Luo and Longxin Wang},
      title = {Efficient Fuzzy Private Set Intersection from Fuzzy Mapping},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1462},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1462}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.