Cryptology ePrint Archive: Report 2009/496

Anonymous Fuzzy Identity-based Encryption for Similarity Search

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

Category / Keywords: public-key cryptography / predicate encryption, anonymous fuzzy IBE, inner-product encryption

Date: received 9 Oct 2009, last revised 12 Jan 2010

Contact author: yzhang4 at cs hku hk

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20100112:145032 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]