PhD thesis: Public-Key Encryption, Revisited: Tight Security and Richer Functionalities

PSL Research University, Paris, France, March 2019

Author: Romain Gay​


Our work revisits public-key encryption in two ways: 1) we provide a stronger security guarantee than typical public-key encryption, which handles many users than can collude to perform sophisticated attacks. This is necessary when considering widely deployed encryption schemes, where many sessions are performed concurrently, as in the case on the Internet; 2) we consider so-called Functional ENcryption, introduced by Boneh, Sahai, Waters in 2011, that permits selective computation on the encrypted data, as opposed to the coarse-grained access provided by traditional public-key encryption. It generalizes the latter, in that a master secret key is used to generate so-called functional decryption keys, each of which is associated with a particular function. An encryption of a message m, together with a functional decryption key associated with the function f, decrypts the value f(m), without revealing any additional information about the encrypted message m. A typical scenario involves the encryption of sensitive medical data, and the generation of functional decryption keys for functions that compute statistics on this encrypted data, without revealing the individual medical records.

In this thesis, we present a new public-key encryption that satisfies a strong security guarantee, that does not degrade with the number of users, and that prevents adversaries from tampering ciphertexts. We also give new functional encryption schemes, whose security relies on well-founded assumptions. We follow a bottom-up approach, where we start from simple constructions that can handle a restricted class of functions, and we extend these to richer functionalities. We also focus on adding new features that make functional encryption more relevant to practical scenarios, such as multi-input functional encryption, where encryption is split among different non-cooperative users. We also give techniques to decentralize the generation of functional decryption keys, and the setup of the functional encryption scheme, in order to completely remove the need for a trusted third party holding the master secret key.