Computer Science Department
School of Computer Science, Carnegie Mellon University
Evaluating Predictaes over Encrypted Data
Keywords: Predicate encryption, appied cryptography, bilinear
Predicate encryption is a new encryption paradigm where the secret
key owner can perform fine-grained access control over the encrypted data.
In particular, the secret key owner can generate a capability corresponding
to a query predicate (e.g., whether an encrypted email contains the keyword
MEDICAL), and the capability allows one to evaluate the outcome of this
predicate on the 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
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.