[Resource Topic] 2009/496: Anonymous Fuzzy Identity-based Encryption for Similarity Search

Welcome to the resource topic for 2009/496

Title:
Anonymous Fuzzy Identity-based Encryption for Similarity Search

Authors: Ye Zhang, Nikos Mamoulis, David W. Cheung, S. M. Yiu, W. K. Wong

Abstract:

In this paper, we consider the problem of predicate encryption and focus on the predicate for testing whether the hamming distance between the attribute X of a data item and a target V is equal to (or less than) a threshold t where X and V are of length m. Existing solutions either do not provide attribute protection or produce a big ciphertext of size O(m2^m). For the equality version of the problem, we provide a scheme which is match-concealing (MC) secure and the sizes of the ciphertext and token are both O(m). For the inequality version of the problem, we give two practical schemes. The first one, also achieving MC security, produces ciphertext with size O(m^{t_{max}}) if the maximum value of t, t_{max}, is known in advance and is a constant. We also show how to update the ciphertext if the user wants to increase t_{max} without constructing the ciphertext from scratch. On the other hand,in many real applications, the security requirement can be lowered from MC to MR (match-revealing). Our second scheme, which is MR secure, produces ciphertext of size O(m) and token of size O((t+1)m) only.

ePrint: https://eprint.iacr.org/2009/496

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 .