Dual System Encryption via Predicate Encodings

Abstract:

In this talk, I will present the notion of predicate encodings, an
information-theoretic primitive reminiscent of linear secret-sharing
that in addition, satisfies a novel notion of reusability. Using this
notion, we obtain a unifying framework for adaptively-secure
attribute-based encryption (ABE) schemes for a large class of
predicates. Our framework relies on Waters' dual system encryption
methodology (Crypto '09), and encompass the identity-based encryption
scheme of Lewko and Waters (TCC '10), and the ABE scheme of Lewko et
al. (Eurocrypt '10). In addition, we obtain several concrete
improvements over prior works. Our work offers a novel interpretation
of dual system encryption as a methodology for amplifying a one-time
private-key primitive (i.e. predicate encodings) into a many-time
public-key primitive (i.e. ABE).

In addition, I will outline some follow-up work on proving
communication complexity lower bounds for predicate encodings. Our
lower bounds indicate that the known trade-offs between ciphertext and
key sizes in several ABE schemes may be in fact inherent.

Based on joint works with Jie Chen (ECNU), Romain Gay (ENS) and
Iordanis Kerenidis (LIAFA).