Functional encryption: definitional foundations and multiparty transformations

Abstract

Classical cryptographic primitives do not allow for any fine-grained access control over encrypted data. From an encryption of some data x, a decryptor, who is in possession of a decryption key, can either obtain the whole data x or nothing. The notion of functional encryption overcomes this drawback and enables access control over encrypted data. In this setting, a setup generator is responsible for generating the public parameters and, so-called, functional keys. These functional keys are decryption keys that are associated with a function f such that, when used in the decryption procedure, the decryptor obtains f(x), which is the result of the function f applied to the encrypted data x. The standard security definition of functional encryption prevents a malicious decryptor from learning more about the encrypted data than what can be obtained from the functional keys it owns. In this thesis, we introduce the notion of consistency, a security definition that protects an honest decryptor against a malicious encryptor and/or setup generator. We formally introduce this notion using different security games and show that our notions are completely separated from existing confidentiality notions. Additionally, we analyze existing schemes and show how they can be modified to achieve consistency. Furthermore, we construct black-box compilers that turn any functional encryption scheme into a consistent one. Finally, we also analyze consistency in the universal composability (UC) framework and show that the consistency games imply UC security. A more general notion of functional encryption is the notion of multi-client functional encryption, which allows a decryptor to evaluate multi-input functions on multiple ciphertexts generated by several different clients. This notion also requires a setup generator that generates the encryption keys for the different clients as well as the functional keys for the decryptor. A corrupted setup generator is able to compromise the privacy of all the clients in the system by generating arbitrary functional keys. To remove this single point of failure, the notion of decentralized multi-client functional encryption has been introduced. In a decentralized multi-client functional encryption scheme the participating clients in the system are responsible for the generation of the encryption and functional keys. In this thesis, we present a compiler that decentralizes any multi-client functional encryption scheme for inner-products, that fulfills certain properties. Furthermore, we show that we can construct a (decentralized) multi-client functional encryption scheme for separable functions, n-input functions that can be written as the sum of n single-input functions, from any general-purpose single-input functional encryption scheme. An interactive version of multi-client functional encryption is the notion of multiparty computation. In multiparty computation several parties can jointly compute a function involving their private inputs by interacting in multiple rounds of communication. We show how we can use functional encryption to amplify existing multiparty computation protocols in terms of their communication complexity. In more detail, we show how to turn a multiparty computation protocol with arbitrary communication complexity into a multiparty computation protocol with a communication complexity only depending on the depth of the circuit that is being computed, while preserving the number of rounds of interaction of the protocol. Furthermore, we present an improved compiler that relies on fully homomorphic encryption, a cryptographic notion that allows for the oblivious evaluation of functions on encrypted data, where the communication complexity of the amplified protocol is completely independent of the circuit that is being computed.