Fully Secure Hidden Vector Encryption

摘要

Predicate encryption is an important cryptographic primitive (see [3,5,9,11]) that enables fine-grained control on the decryption keys. Roughly speaking, in a predicate encryption scheme the owner of the master secret key Msk can derive secret key Sk_P, for any predicate P from a specified class of predicates P. In encrypting a message M, the sender can specify an attribute vector x and the resulting cipher-text X can be decrypted only by using keys Sk_P such that P(x) = 1. Security is modeled by means of a game between a challenger C and a PPT adversary A that sees the public key, is allowed to ask for keys of predicates P of his choice and gives two challenge vectors x_0 and x_1. A then receives a challenge ciphertext (an encryption of a randomly chosen challenge vector) and has to guess which of the two challenge vectors has been encrypted. The adversary A is allowed to ask queries even after seeing the challenge ciphertext. In the unrestricted queries model, it is required the adversary A to ask for keys of predicates P that do not discriminate the two challenge vectors; that is, for which P(x_0) = P(x_1). It can be readily seen that this condition is necessary. In this paper, we consider hidden vector encryption (HVE in short), a notable case of predicate encryption introduced by Boneh and Waters [5] and further developed in [16,10,15]. In a HVE scheme, the ciphertext attributes are vectors x = (x_1, ..., x_l) of length l over alphabet ∑, keys are associated with vectors y =