Paper 2009/496

Anonymous Fuzzy Identity-based Encryption for Similarity Search

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


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)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
predicate encryptionanonymous fuzzy IBEinner-product encryption
Contact author(s)
yzhang4 @ cs hku hk
2010-01-12: last of 2 revisions
2009-10-14: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.