From Selective to Adaptive Security in Functional Encryption

Abstract: In a functional encryption (FE) scheme, the owner of the secret key can generate restricted decryption keys that allow users to learn specific functions of the encrypted messages and nothing else. In many known constructions of FE schemes, security is guaranteed only for messages that are fixed ahead of time (i.e., before the adversary even interacts with the system). This so-called selective security is too restrictive for many realistic applications. Achieving adaptive security (also called full security), where security is guaranteed even for messages that are adaptively chosen at any point in time, seems significantly more challenging. The handful of known adaptively-secure schemes are based on specifically tailored techniques that rely on strong assumptions (such as obfuscation or multilinear maps assumptions).

We show:
- any sufficiently-expressive selectively-secure FE scheme can be transformed into an
adaptively-secure one without introducing any additional assumptions.
- how to construct FE schemes for arbitrary circuits starting from ones for shallow
circuits (NC1 or even TC0).

This is joint work with Zvika Brakerski, Gil Segev and Vinod Vaikuntanathan