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

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.

Metadata
Available format(s)
PDF PS
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
2009-10-14: received
See all versions
Short URL
https://ia.cr/2009/496
License
Creative Commons Attribution
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},
      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.