1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I edit the question to mentioning two papers. $\endgroup$ – kawsaw Sep 9 at 12:09
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thank you for the response. So, the evaluation key can be the circuit of the function that a user needs to perform on cipertexts? $\endgroup$ – kawsaw Sep 13 at 18:15
  • $\begingroup$ No. The circuit is just one possible way to represent the function to be evaluated, so, it is not a key. The evaluation key is "another public key" created using only the private key and it is general, that is, once it is created, it can be used to evaluate any circuit. $\endgroup$ – Hilder Vítor Lima Pereira Sep 14 at 9:58
  • $\begingroup$ Thank you for the response. Could you please see the Distributed-Evaluation Homomorphic Encryption Definition , p7, in [researchgate.net/publication/… ]. Here, the evaluation key does not seem to be related to noise but to the function to perform. Was I correct? $\endgroup$ – kawsaw Sep 15 at 9:16
  • $\begingroup$ But in definition 2 the function that generates a pair of evaluation keys does not receive the program. Anyway, it seems that the concept of "evaluation keys" used in this paper is not the same as in homomorphic encryption schemes, because those are keys of a homomorphic Secret Sharing scheme. It is not correct to compare them. $\endgroup$ – Hilder Vítor Lima Pereira Sep 15 at 11:04
1
$\begingroup$

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 their 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 it is really trusted or covert adversary, anyway in FHE we usually assume that 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 decrypt 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 key 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 users private key where each removes one layer of the onion.

Evaluation key as defined in Efficient Fully Homomorphic Encryption from (Standard) LWE

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.

Evaluation key can be created during the key-gen and transmitted the server with the circuit if the bootstrapping is needed.

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

$\endgroup$
  • $\begingroup$ We can use evaluation keys even if we perform no bootstrapping... $\endgroup$ – Hilder Vítor Lima Pereira Sep 9 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.