Efficient Hidden Vector Encryption for Conjunctive Queries on Encrypted Data

Predicate encryption has received considerable attention in applications where private and sensitive data about users can be stored in untrusted database (DB) servers. It allows users to store encrypted data at DB servers, and yet retain the ability to search those databases without revealing anything else about the encrypted data. Hidden Vector Encryption (HVE) is a type of predicate encryption that supports the fine-grained conjunctive combination of equality queries, comparison queries, and subset queries on encrypted data. The currently known HVE schemes, which are all pairing-based, either work in composite-order groups or require a token size of O(ℓ) and O(ℓ) pairing computations for one search query with ℓ conjuncts. In this paper, we present a new HVE scheme that not only works in prime-order groups but also requires a token size of O(1) and only O(1) pairing computations regardless of ℓ. Our HVE construction also yields a more efficient, anonymous, identity-based encryption scheme than existing schemes, which is secure in the standard model. To achieve our goal, we introduce novel techniques for both hiding attributes in prime-order groups and reducing the number of pairing computations to O(1). Our techniques are quite general so that they can be applied to both symmetric and asymmetric bilinear maps.