A gentle introduction to functional encryption
Nov 25, 2024
Functional encryption (FE) can be seen as a generalization of public key encryption (PKE) allowing for a more fine-grained control of the decryption capabilities of third parties.
In PKE the public key $p_k$ is used to hide a value $x$ inside a ciphertext $ct$ (encryption algo) while the secret key $s_k$ is used to retrieve $x$ from $ct$ (decryption algo). PKE enforces an all or nothing access rule - one can either decrypt and read the entire plaintext or learn nothing at all about the plaintext. In FE the secret key $sk_{f}$ is associated to a specific function $f$ such that the decryption function returns $f(x)$. You can notice how PKE can be derived from FE by setting $f$ as the identity function.
More explicitely, here you see the different “APIs” between the two encryption protocols. The setup phase of FE generates a master secret key $msk$, which can be used in the keygen phase to derive the secret key $sk_{f}$ for a specific function $f$. The encryption algorithm follows the same logic, while the decryption requires the function secret key $sk_{f}$ to obtain $f(x)$.
Informally, the security of a FE scheme requires that an adversary learns nothing about $x$ more than what is revealed by $f(x)$. [BSW10] provides a more formal security definition of such scheme. I’ll also try to explain it in detail later. Now, let’s consolidate the understanding of the encryption scheme by considering an example application.
Application example
Let’s consider an hospital that custodies plenty patient records and there are $n$ categories of professionals with different access levels to those data. In such scenario the hospital administration will run the setup phase and later create different function secret keys $sk_{f_1}, \dots, sk_{f_i}, \dots, sk_{f_n}$ such that each function $f_i$ encodes a specific access policy on the patient record. The administration later distributes the secret keys to the respective categories. The patient records are encrypted under $pk$ and each professional is able to perform a decryption function that only reveals the information that they are allowed to access and nothing else.
In such a setup the administration has to generate a single encrypted record that can serve multiple access levels. This is more efficient than traditional symmetric/asymmetric encryption which would have required the administration to perform $n$ encryptions.
Differences with fully homomorphic encryption
If you are familiar with fully homomorphic encryption (FHE), it might be interesting to analyze the differences and similarities between these two primitives. Both allow them to perform functions on encrypted data, but the setup and the use cases they serve are radically different. Typically, FHE applications are designed for outsourcing computation such that:
- Alice performs the setup and encrypts her data $x$ and sends the resulting ciphertext $ct$ to Bob
- Bob evaluates the function $f$ over the ciphertext $ct$ to obtain $ct’$ and sends the result to Alice
- Alice decrypts the ciphertext and obtains $f(x)$
In FHE, the function $f$ to be performed on encrypted data (evaluation phase) is arbitrary: Bob can apply any arithmetic function on top of the ciphertext $ct$, which can also be private to Alice. In contrast, in FE, the set of functions that can be performed on the ciphertext is bounded by the function secret keys generated by the master. On the other hand, the FHE evaluation function returns another ciphertext, which requires Alice’s intervention to decrypt it. In FE, no further interaction is required to access $f(x)$ as the evaluation and decryption function are performed simultaneously.
In short, FHE always requires an interaction with the key owner to obtain $f(x)$ but the function $f$ can be arbitrary (and, optionally, secret). In HE, no interaction with the key owner is required to obtain $f(x)$ but the set of functions that can be performed is limited.
Security definition of FE
The security of FE is defined under the notion of indistinguishability under chosen plaintext attack (IND-CPA). The security is demonstrated via a game between an adversary $A$ and a challenger. The logic of the game is similar to the one applied to prove the semantic security of a PKE scheme, as illustrated below.
Let’s analyze the PKE case first. For $b = { 0; 1 }$ the experiment $b$ proceeds as follows::
- The challenger generates a key pair $(pk, sk)$ using function $G()$ and gives $pk$ to $A$
- $A$ receives the public key $pk$
- $A$ then chooses two messages $m_0$ and $m_1$ of equal length and share them with the challenger
- The challenger encrypts message $m_{b}$ (where $b$ is either $0$ or $1$ but $A$ doesn’t know it) using the public key: $c ← E(pk, m_{b})$
- $A$ receives the ciphertext $c$ and outputs a guess $b’ \in {0,1}$
The scheme $E$ identified starting from its functions $(G, E,D)$ is semantically secure if no efficient (polynomial-time) adversary $A$ can distinguish between the encryption of $m_0$ and $m_1$. Mathematically, this is expressed as: $$|Pr[EXP(0)=1] - Pr[EXP(1)=1]| < \text{negligible}$$
Where $Pr[EXP(0)=1]$ measures the probability that the adversary incorrectly outputs 1 in the experiment 0 and $Pr[EXP(1)=1]$ the probability that the adversary correctly outputs 1 in the experiment 1. In other words, the probability of the adversary correctly guessing which message was encrypted should be very close to random chance. In practice, this ensures that an adversary cannot learn anything about the plaintext by looking at the ciphertext, even if they can choose the messages to be encrypted. As noted by Morrolan, this security property holds iff the encryption scheme is non-detrministic i.e. two encryptions of the same plaintext under the same public key must produce different ciphertexts with overwhelming probability.
In FE, the game is just slightly different. For $b = { 0; 1 }$ the experiment $b$ proceeds as follows:
- The challenger generates a key pair ${ pk, msk }$ to $A$
- $A$ adaptively submit queries for different function $f_1, f_2, \dots, f_i$ to the challenger and receives the corresponding function secret keys $sk_{f_1}, sk_{f_2}, \dots, sk_{f_i}$
- $A$ then chooses two messages $m_1$ and $m_2$ such that $f_i(m_1) = f_i(m_2)$ and share them with the challenger
- The challenger encrypts message $m_{b}$ (where $b$ is either $0$ or $1$ but $A$ doesn’t know it) using the public key: $c ← E(pk, m_{b})$
- $A$ receives the ciphertext $c$ and outputs a guess $b’ \in {0,1}$
The adversary is able to decrypt the ciphertext $c$ and obtain $f(m_{b})$ but, similarly to before, cannot distinguish if the ciphertext $c$ is an encryption of $m_1$ or of $m_2$. This proves the definition of security that was given in the introduction. To be even more precise, [BSW10] demonstrates that this security definition is inadequate for specific functions $f$ and provides a more rigorous security definition in the paper.
Conclusions
Aside from its relevance to real-world applications for computing on encrypted data, as described in this blogpost, FE has proved to be a powerful tool in the theory of cryptography and can be used to build advanced primitives such as Indistinguishability Obfuscation (iO), which is considered essentially “crypto-complete” by its ability to instantiate almost every known cryptographic primitive. In particular, according to Sora’s presentation, iO can constructed using recursive FE. The actual construction of FE is reserved for a follow-up blogpost.