What is Homomorphic encryption evaluation key

Question

In some homomorphic encryption schemes (e.g Multi-key fully homomorphic encryption report, Computing Blindfolded: New Developments in Fully Homomorphic Encryption), it defines an encryption key, a decryption key, and an evaluation key to perform an evaluation f on the encrypted data. Could you please explain what is the difference between the evaluation key and the other keys?

Answer 1

In short

Public key is used to encrypt, private key is used to decrypt, and evaluation key is used to perform homomorphic operations (usually, homomorphic product or, the somehow equivalent operation, a logic AND gate).

In detail

Public and private keys in homomorphic encryption (HE) schemes are just the same as in other types of schemes.

The evaluation key ($evk$) is also public, it is typically generated using the private key, and it is used to control the noise growth or the ciphertext expansion during homomorphic evaluation.

Some schemes have a "Key-switching" key instead of the evaluation key, but they are more or less the same. For instance, in the description of FV and YASHE, you can see that to perform a homomorphic product, one first multiplies the ciphertexts, $\tilde{c}_{mult} := c_1 \otimes c_2$, then uses this "extra public key" to adjust $\tilde{c}_{mult}$, that is, to get a ciphertext $c_{mult}$ with the correct dimension and that can be decrypted using the original secret key.

So, in general, this is how you use $evk$: you perform a homomorphic operation that introduces a lot of noise or that generates a ciphertext in higher dimension, then you perform an extra operation using $evk$ to "correct" that ciphertext.

As an extra example, take a look to FHEW Library Interface and you will see that the NAND gate uses $evk$, but the NOT gate does not.

Further observations

• If you bootstrap, then you typically need $evk$, since you need it to perform homomorphic evaluations in general and bootstrapping is the homomorphic evaluation of the decryption circuit.

• In principle, there is no special relation between multi-key HE schemes and evaluation keys (FHEW is not multi-key and also has an $evk$).

• Even if the scheme is symmetric (i.e., does not have a public encryption key), it may still have evaluation key.

• Some schemes do not have evaluation key (e.g., GSW).

Answer 2

In Normal FHE, there is one entity who wants to evaluate circuits on the cloud without revealing their data. In this case, there is one public and private key of the entity. The entity encrypts the data by using the public key and send the circuit $\mathcal{C}$ to $\text{EVAL}$

$$\text{EVAL}( \mathcal{C}(c_1,\ldots,c_l,k_{pub})$$ where $c_i = Enc(k_{pub},p_i)$.

In Multi-key fully homomorphic encryption each user has sensitive data not want to reveal to others, (age,sex, salary, etc..) but they want to evaluate a circuit on their data. Of course, they can send the data to a trusted user who can calculate and return the value. The question is whether it is a trusted or covert adversary, anyway in FHE we usually assume that the evaluator is semi-honest. Instead of trusting the idea in Multi-key FHE, each user encrypts his/her data with his/her public key and decrypts his/her data with his/her private key.

$$C_j = Enc(k_{pub_j},P_j)$$ where $k_{pub_j}$ is the public key of the user $j$.

Now if you look at you will see that users send their public keys for evaluation. Since the data is encrypted with different public keys the onion encryption is defined. This is a series of operations to unify the data under the same onion of encryptions. After this, the $\mathcal{C}$ can be evaluated and the result can be decrypted by the user's private key where each removes one layer of the onion.

Evaluation key as defined in Fully Homomorphic Encryption without Bootstrapping

Bootstrapping “refreshes” a ciphertext by running the decryption function on it homomorphically, using an encrypted secret key (given in the evaluation key), resulting in reduced noise.

An evaluation key can be created during the key-gen and transmitted to the server with the circuit if the bootstrapping is needed. Evaluation key is also used for the computations, so most of the time is already sent the server.

And in Multy-FHE each user has sent their evaluation key, too.

For each of those keys the ciphertext is ”corrected” with the evaluation key, such that the power of this key goes down in the new key