Evaluating predicates over encrypted data

The high-level goal of this thesis is to build predicate encryption systems that are efficient, support expressive queries and rich operations. Our contributions are summarized below: (1) We propose a predicate encryption scheme supporting multi-dimensional range queries. Prior to this work, researchers have constructed schemes support equality tests. Hence, our scheme supports more expressive queries than before. At the core of this construction is a technique to support conjunctive queries without leaking the outcome of each individual clause. (2) We study how to delegate capabilities in predicate encryption schemes. To demonstrate why delegation may be interesting, imagine that Alice has a capability, and she wishes to delegate to Bob a more restrictive capability allowing him to decrypt a subset of the information Alice can learn about the plaintext encrypted. We propose a security definition for delegation, and build a scheme supporting delegation and conjunctive queries. (3) Most prior work focuses on hiding the plaintext (encoded in the ciphertext), but does not provide guarantees about the secrecy of the queries (encoded in the capabilities). In other words, given a capability, one might be able to infer from it what the query predicate is. We study how to hide the query predicates, and propose a scheme supporting inner-product queries that hides the query predicates in addition to the plaintext.