Efficient Fuzzy Private Set Intersection from Fuzzy Mapping

DOI码：

10.1007/978-981-96-0938-3

发表刊物：

Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security

刊物所在地：

Kolkata, India

关键字：

Fuzzy private set intersection;Fuzzy mapping;Multi-query fuzzy reverse private membership test

摘要：

Private set intersection (PSI) allows Sender holding a set X and Receiver holding a set Y to compute only the intersection X∩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∞ 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 Lp∈[1,∞] distances. For Hamming distance, our protocol is the first one that achieves strict linear complexity with input sizes. For Lp∈[1,∞] distance, our protocol is the first one that achieves linear complexity with input sizes, dimension, and threshold.

合写作者：

Lin Qi, Xiang Liu, Yuanchao Luo, Longxin Wang

第一作者：

Ying Gao

论文类型：

会议论文

通讯作者：

Ying Gao

页面范围：

36–68

ISSN号：

978-981-96-0937-6

是否译文：

否

发表时间：

2024-12-12