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
-
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} }