Introduction to FE

What is functional encryption (FE)?

Functional encryption overcomes all-or-nothing limitations of classical encryption schemes where the relationship dec(enc(x)) = x holds. In FE, decryption does not output x but f(x) for some function f, e.g. dec(enc(x)) = f(x). To be precise, all FE schemes require derivation of a special key f_key used for decryption, so the relationship is actually dec(enc(x), f_key) = f(x).

About the function f

For practical purposes, the function f cannot be arbitrary. Instead, existing FE schemes are tailored for specific classes of functions. So far, efficient FE schemes only exist for linear and quadratic polynomials. Although FE schemes based on multi-linear maps and indistinguishability obfuscation that support more general functions already exist in theory, currently they are far from being practical.

GoFE and CiFEr offer different implementations of these two classes of FE schemes:

• Inner product schemes where f: x → = <x, y> = x₁y₁ + ... + x_ny_n. Here x and y are vectors, e.g. x = (x₁, ..., x_n) and y = (y₁, ..., y_n). One of the vectors, let's say x, is encrypted. The decryption gives us the inner product <x, y>, and we learn nothing about the original vector x (other than what can be learned from the function itself).
• Quadratic polynomials schemes where f: (x,y) → Σ_i,j f_i,jx_iy_j = x^T F y, x and y are vectors, and F = (f_i,j) is a matrix.

Note that function f does not need to be known prior to encryption, as it is only relevant for decryption.

Who participates in FE?

FE schemes involve the following three entities:

• Encryptor - an entity that encrypts the data, and sends the cipher to decryptor.
• Decryptor - an entity that decrypts the data received from encryptor.
• A trusted entity that generates cryptographic keys for encryption (master keys) and decryption (FE keys).

Single input and multi input schemes

With respect to the number of encryptors and the nature of function f, we divide FE schemes into:

• single input schemes, where a single encryptor encrypts data x and a single decryptor that computes f(x).
• multi input schemes where there are n encryptors, each encrypting their own data x_i, and function f = f(x₁, . . . , x_n) computed by a single decryptor. Multi input schemes make FE well suited for many interesting real life problems such as data mining over encrypted data.

Every multi input scheme operates on a series of instances of a particular underlying single input scheme.

Security levels of FE schemes

With respect to assumptions in security proofs of FE schemes, we differentiate between schemes with:

• selective security under chosen-plaintext attacks (s-IND-CPA security) schemes, which are secure against selective adversaries. This means the adversary in the security game commits to the challenge (messages m0 and m1) before seeing public parameters of the scheme.
• adaptive security under chosen-plaintext attacks (IND-CPA security) and simulation based security schemes, which make no such assumption and achieve full security.