### Anonymous Fuzzy Identity-based Encryption for Similarity Search

Ye Zhang, Nikos Mamoulis, David W. Cheung, S. M. Yiu, and 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
predicate encryptionanonymous fuzzy IBEinner-product encryption
Contact author(s)
yzhang4 @ cs hku hk
History
2010-01-12: last of 2 revisions
See all versions
Short URL
https://ia.cr/2009/496

CC BY

BibTeX

@misc{cryptoeprint:2009/496,
author = {Ye Zhang and Nikos Mamoulis and David W.  Cheung and S. M.  Yiu and W. K.  Wong},
title = {Anonymous Fuzzy Identity-based Encryption for Similarity Search},
howpublished = {Cryptology ePrint Archive, Paper 2009/496},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/496}},
url = {https://eprint.iacr.org/2009/496}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.