CMU-CS-06-135
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-06-135

Anonymous Multi-Attribute Encryption with
Range Query and Conditional Decryption

John Bethencourt, T-H. Hubert Chan
Adrian Perrig, Elaine Shi, Dawn Song

May 2006

CMU-CS-06-135.ps
CMU-CS-06-135.pdf


Keywords: Range query, conditional decryption, anonymous identity-based encryption, multi-dimensional lattice

We introduce the concept of Anonymous Multi-Attribute Encryption with Range Query and Conditional Decryption (AMERQCD). In AMERQCD, a plaintext is encrypted under a point in multidimensional space. To a computationally bounded adversary, the ciphertext hides both the plaintext and the point under which it is encrypted. In a range query, a master key owner releases the decryption key for an arbitrary hyper-rectangle in space, thus allowing decryption of ciphertexts previously encrypted under any point within the hyper-rectangle. However, a computationally bounded adversary cannot learn any information on ciphertexts outside the range covered by the decryption key (except the fact that they do not lie within this range). We give an efficient construction based on the Decision Bilinear Diffie-Hellman (D-BDH) and Decision Linear (D-Linear) assumption.

38 pages


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu