## Predicate encryption systems. No query left unanswered

##### Abstract

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]