Forget Homomorphic Encryption, Here Comes Functional Encryption

Have you ever heard of Functional Encryption (FE)? If so, you may be associating it with some sort of homomorphic encryption, which is not wrong, but not exactly right neither.

Let us see today what FE is along with a few examples, roughly how it differs from Fully Homomorphic Encryption, and how the FENTEC project is working on it!

Now, let us define what we mean when we are talking about FE. It is only recently, in 2010, that Dan Boneh, Amit Sahai and Brent Waters formalized the notion of functional encryption. We can roughly describe FE by saying it is a public-key encryption scheme with different decryption keys allowing a user to learn specific functions of the encrypted data.

So, in an FE scheme for function $F(\cdot, \cdot)$ , an authority holding a master key generates a key $s_k$ that enables the computation of the function $F(k, \cdot)$ on encrypted data, so that an evaluator knowing a ciphertext $c$ of the data $x$ and the key $s_k$ is able to compute $F(k,x)$ , but without being able to learn anything more than the result of the function evaluation about $x$ .

FE vs FHE, why the ache H?

If you are familiar with the concept of (Fully) Homomorphic Encryption, (F)HE, it is interesting to draw the following parallel:

With FHE one can compute arbitrary functions on encrypted data without decrypting that data. This is very interesting for delegating computation to untrusted third parties. The downside (depending on your use case) of FHE being that the result is still encrypted and thus needs to be sent back to the entity holding the private key in order to decrypt the result of the computation. We can somehow represent the FHE process as follows, with $E$ being an encryption scheme and $F$ being the function we want to compute on the encrypted data:

$E(x_1), E(x_2), ..., E(x_n) \rightarrow E(F(x_1,x_2, \cdots, x_n))$

On the other hand, with FE, the result is directly accessible in plaintext after computation, which means we could see it as follows:

$E(x_1), E(x_2), \cdots , E(x_n) \rightarrow F(x_1,x_2, \cdots, x_n)$

In some sense, we can see FE as being a scheme that does both evaluation and decryption of the result of a function at the same time, without leaking the private key allowing to decrypt the data and without leaking information about the plaintexts $x_1, x_2, \cdots, x_n$ other than the result of their evaluation by the function $F$ .

Obviously, we don’t want everyone to be able to evaluate any function they might want to, as otherwise it would be easy to leak information about individual plaintexts. (Look! I’d like to evaluate the identity function, pretty please.) Hence, only the private key holder is actually able to decrypt $E(x_i)$ , and only they can generate the evaluation keys for specific functions of their choice. This means that functional encryption requires a “central authority” to issue the “evaluation key” to the parties in charge of the functional evaluation.

So, functional encryption per se is a generalization of the notion of public-key encryption, which allows users to delegate to third parties the computation of certain classes of functions of the encrypted data by generating specific secret keys for these functions. Unlike standard encryption schemes, it allows for a more fine-grained control of the decryption capabilities of third parties.

Functional Encryption is extremely useful since it basically allows us to intentionally leak some information about encrypted data to chosen users. For example, we could get the average value of a set of encrypted data without revealing the data itself, or we could go further and obtain even more statistical data about an encrypted dataset. With the current privacy concerns and requirements raised by new laws such as GDPR, the need for efficient FE schemes appears even more clearly as it would allow some processing on encrypted data to be done by certain third parties without leaking the actual plaintexts to anyone. This means we could go further than pseudonymization of personal data, to ensure some kind of stricter confidentiality! The FENTEC blog also has an entry about cryptography and laws if that’s interesting to you.

The FENTEC project

Now, you may wonder: what is this FENTEC project he’s talking about? Well, it is a project that received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 780108, and whose goal is to further develop Functional Encryption Technologies as an alternative to the all-or-nothing approach of traditional encryption systems. (That is: either you have encryption, or you don’t, there were no middle ground until Functional Encryption.)

The project brings together multiple universities and industrial partners in order to design and implement efficient, innovative FE systems which are application oriented and can be used in a wide range of scenarios. Kudelski Security’s research team is glad to be one of the industrial partners taking part in the FENTEC project, which will last 36 months. The project officially started in January 2018 and will thus end in December 2020.

Back to FE

Due to its generality, functional encryption encompasses and unifies many other advanced encryption schemes that used to be studied independently, such as identity-based encryption, searchable public-key encryption, hidden-vector encryption, identity-based encryption with wildcards, attribute-based encryption, and inner-product functional encryption.

While FE schemes are still very young, a lot of things happened since 2010 and there are now quite a few interesting schemes allowing for functionalities that seemed hard to achieve 8 years ago. It has now come to a point where certain cryptography conferences even have a session named “Functional Encryption”!

Let us take a look at several different types of functional encryption schemes. For example:

Inner product functional encryption (IPFE) schemes, where the plaintext is a vector and the encrypted data can be used along with an evaluation key to compute the inner product of the said vector with another vector. There are multiple variants of IPFE actually: multi-clients, multi-inputs, decentralized, function hiding, etc.
Attribute-based encryption (ABE) schemes, where the encrypted data is linked with a set of attributes and secret keys along with certain policies that allow to control which ciphertexts can be decrypted depending on the attributes we possess.
“General-purpose” FE schemes, that allow to evaluate any kind of function $f$ (or circuit, depending on the scheme) on the encrypted data $\mathrm{Enc}(x)$ . ~~(I wish we’d call these “Fully Functional Encryption schemes”, even if they don’t really work in practice)~~

However, it is also important to notice here that while there has been a lot of work focused on the theoretical aspects of FE in order to go as far as we can, all the general-purpose FE schemes are currently too inefficient for practical usages. This is also one of the focuses of the FENTEC project: making FE usable in practice by designing and implementing practical schemes that can be used in industrial use-cases. This objective is supported by the design and implementation of new schemes, allowing for richer functionalities and practical instantiations, but also by designing dedicated co-processors that can further accelerate the required computations, in order to be able to bridge the theory with the practice. You can read more about the hardware components of the project in this FENTEC blog post.

Wanna use FE today? Please, do.

But what if you want to use FE tomorrow? Well, that shouldn’t be a problem! Indeed, in the frame of the FENTEC project, the team at XLAB has been implementing many of the schemes designed by the partner universities in a C library “CiFEr” and a Go library “GoFE“, that are ready to go!

You can read more about the FENTEC libraries on the FENTEC blog, or you can go directly to Github to start playing with CiFEr & GoFE. By the way, guess what? We tested it, and it even runs in your browser using WASM, shall you so wish!

There even are a couple examples available on the FENTEC’s Github repositories, namely:

How an Attribute-Based Encryption scheme can help managing access to clinical data: https://github.com/fentec-project/Selective-Access-to-Clinical-Data
How an Inner Product Functional Encryption scheme can help building a heat-map of the location of users in a fully anonymous way: https://github.com/fentec-project/FE-anonymous-heatmap
How a Quadratic Function Encryption scheme can enable machine learning on encrypted data, allowing us to do OCR of handwritten digits without leaking the actual handwriting: https://github.com/fentec-project/neural-network-on-encrypted-data

The gory details: the guts of a FE scheme

Among currently implemented schemes you can find a lot of “Inner Product Functional Encryption” ones. But what does it mean? Well, exactly what it says: these are schemes that allow a third party to compute the inner product of two vectors using FE.

Let’s say that you would like to encrypt a given vector $a$ and obtain its inner product with a vector $y$ . First, we need to have a central authority in order to implement functional encryption.

In this case, the central authority would issue a “master public key” $mpk$ , as well as an evaluation key $z_y$ for a given vector $y$ . Then, anybody knowing the public key could encrypt a vector $a$ , allowing any third party in possession of the evaluation key $z_y$ would then be able to compute the values of $\langle a, y \rangle$ when provided with $E_{mpk}(a)$ , without learning anything about the vector $a$ .

However, note that in this FE scheme, the vector $y$ corresponding to the evaluation key $z_y$ has to be known by the third party in order to evaluate the inner product. That is: only the vector $a$ is remaining secret.

Now, what if you want both vectors $a$ and $y$ to remain secret while you still want that third party to evaluate their inner product?

Thankfully, this is a field of research that has also known tremendous improvement over the past years and is named “FE with function hiding”. Basically, an inner product encryption scheme is “function-hiding” if the keys and ciphertexts reveal no additional information about both vectors $a$ and $y$ beyond their inner product $\langle a,y\rangle$ . Newer inner product FE schemes are more and more featuring function hiding.

To wind-up

While it is still young, Functional Encryption has many interesting usages we can foresee. Among them, one that seems particularly interesting to us is the possibility to move the decision making process based on end-to-end encrypted data from the back-end systems to some gateways in complex networks. We call this “local decision making“, and being able to enable gateways to perform such local decision making is a big step forward to secure IoT networks and other highly decentralized networks that might want to implement end-to-end encryption, without losing too much decision capabilities at the gateways level.

At Kudelski Security, in the frame of the FENTEC project, we are currently working on a prototype leveraging an inner product FE scheme in order to detect motion in a video stream between a camera and a backend system at the gateway level, using the so-called “motion vectors” that are present in the H.264/MPEG-4 AVC standard.

Visualization of motion vectors in a frame from a H.264 encoding of the open shortfilm Big Buck Bunny: (c) copyright Blender Foundation | http://www.bigbuckbunny.org

Notice how motion vectors are good candidates for application of an Inner Product Functional Encryption schemes, as Inner Products are defined on vectors spaces! We are still exploring the best movement detection methods, but are looking forward to having a fully working prototype leveraging FE to detect motion by the end of next year!

In case you’d like to stay tuned for more about FE, FENTEC and motion detection, don’t hesitate to follow us on Twitter, or to follow the FENTEC project!