Investigating the Security of Functional Encryption

Date: 
Wednesday, July 1, 2020

Author: Hendrik Waldner & Aggelos Kiayias (University of Edinburgh Research Explorer) 

The concept of Functional Encryption has already been discussed in previous posts. In this post we will discuss the notion of security that a functional encryption scheme should offer to be useful in practice.

As a recap, functional encryption is a generalization of public key encryption that allows the delegation of fine-grained access control over ciphertexts to different users. A normal public key encryption scheme makes use of two different keys, a public key and a secret key, as well as two algorithms, the encryption and decryption procedure. The encryption algorithm, together with the public key, is used to encrypt a message and the decryption algorithm, together with the secret key, is used to decrypt a ciphertext. A functional encryption scheme is equipped with an additional key generation algorithm. This key generation algorithm takes as an input the secret key and a function and outputs a so-called functional key. This functional key can be used in the decryption procedure to output the corresponding function applied on the underlying message of the ciphertext.

Security for such a scheme is usually defined with respect to a malicious function evaluator user. In more detail, a malicious Eve who owns several functional keys for different functions should only be able to learn what is implied by the output of those functions applied on the underlying plaintext of a ciphertext and nothing beyond that. To get a better intuition about this security definition, let us consider the following example of a privacy preserving spam filter:

Alice wants to send an encrypted email to Bob and the email provider that delivers this email should be able to detect if the email sent by Alice contains spam or not. To make this happen in a privacy preserving manner the email provider should learn nothing besides the fact if the email is spam or not. We can easily solve this problem using functional encryption in the following way: Bob creates a public key and a secret key, sends the public key to Alice and uses the secret key to generate a functional key for the spam detection function which he sends to the email provider. Whenever Alice wants to email Bob, she uses the public key to encrypt it and sends it to the email provider. The email provider uses its functional key to detect if the email is spam. In the case that the email is spam it is discarded and if it is spam-free it is forwarded to Bob.

If the used functional encryption scheme is secure, privacy for the communication between Alice and Bob is achieved and the email provider does not learn anything more than the fact that the e-mail is spam or not. But does this prevent Bob from receiving spam sent by Alice? Perhaps surprisingly, the answer to this question is no. This can be seen by considering that Alice need not behave according to the protocol: a malicious Alice may not use the encryption algorithm to generate the encryption of her email, but some other method of her own design that  generates a ciphertext. Now, according to the security definition, we have no guarantee about the behaviour of the functional key on this message. The functional key might tell the email provider that the message does not contain spam, but when Bob uses its secret key to decrypt, he receives an email that looks like spam to him. These kinds of attacks are not captured by the standard security definition of functional encryption.

A rigorous definitional treatment for security in the case of other malicious parties than the functional evaluator, i.e. ciphertext and/or functional key generator, has been recently released in the work of Consistency for Functional Encryption within the FENTEC project. In this work, we answer the question laid out above and provide the necessary security definitions that capture the above mentioned issues of the standard definition. The consistency definition that achieves security in the case of a dishonest input provider, which also captures the above described example, is called input consistency. In a nutshell, a functional encryption scheme achieves input consistency, if it is not possible to generate a ciphertext that decryption behaviour is unexplainable for a set of functional keys. This means that there should always exist a message that explains the resulting functional outputs. Besides this, we also introduce the notion of strong input consistency, for a malicious ciphertext and key generator, as well as setup consistency, for a malicious key generator, i.e. public key and secret key, as well as functional keys. In addition to the definitional treatment, we also present a security analysis of existing functional encryption schemes with respect to consistency, as well as black-box compilers that, applied on top of a functional encryption scheme, achieve all the three different notions of consistency.

 For more details, we refer to the paper which can be found here.