2010 | OriginalPaper | Chapter
Anonymous Fuzzy Identity-Based Encryption for Similarity Search
Authors : David W. Cheung, Nikos Mamoulis, W. K. Wong, S. M. Yiu, Ye Zhang
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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^{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.