Anonymous fuzzy identity-based encryption for similarity search

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(2 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 a practical scheme, also achieving MC security, which produces a ciphertext with size O(m tmax) 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. © 2010 Springer-Verlag.