Fully secure hidden vector encryption under standard assumptions

Hidden Vector Encryption (HVE) is a special type of predicate encryption that can support conjunctive equality and range searches on encrypted data. All previous HVE schemes were proven to be either selectively secure or weakly attribute-hiding. In this paper, we first construct a new HVE scheme that is fully secure under standard assumptions. Our HVE scheme, which is based on bilinear maps (pairings), provides efficiency advantages in that it requires O(1)-sized private keys and O(1) pairing computations for decryption, regardless of both the number of conjunctives and the dimension of vectors. To achieve our goal, we develop a novel technique to realize a tag-based dual system encryption in prime-order groups and show how to hide vector components and compress tag values into one.