Predicate encryption systems. No query left unanswered

Predicate encryption is an important cryptographic primitive (see [7, 14, 28]) that enables fine-grained control on the decryption keys. Let T be a class of binary predicates. Roughly speaking, in a predicate encryption scheme for the owner of the master secret key Msk can derive secret key Sk_P , for any predicate P in T. In encrypting a message M, the sender can specify an attribute x and the resulting ciphertext X can be decrypted only by using keys Sk_P such that P(x) = 1. Our main contribution is the first construction of a predicate encryption scheme that can be proved fully secure against unrestricted queries by probabilistic polynomial-time adversaries under non-interactive constant sized (that is, independent of the length of the attribute vectors) hardness assumptions on bilinear groups. Specifically, we consider Hidden Vector Encryption (HVE for short), a notable case of predicate encryption introduced by Boneh and Waters [14]. In a HVE scheme, the ciphertext attributes are vectors x of some fixed length l over some alphabet A, keys are associated with vectors y of the same length l over the alphabet B that equals A enlarged with the special symbol '*', and we consider the Match(x,y) predicate which is true if and only if, for all i, when y_i is different from *, then x_i = y_i. Previous constructions limited the proof of security to restricted adversaries that could ask only non-matching queries; that is, for challenge attribute vectors x_0 and x_1, the adversary could ask only keys for vectors y such that Match(x_0, y) = Match(x_1, y) = 0. Generally speaking, restricted adversaries can ask only queries that do not satisfy neither of the challenge attributes. At time of writing, the construction of schemes secure against unrestricted adversaries was an open problem, not just for HVE, but for any non-trivial predicate encryption system and a candidate solution for HVE is presented in this thesis. Beyond that, we will also discuss other kinds of predicate encryption systems, their security notions and applications. [edited by Author]