Search code examples
c++seal

Relinearizing one Ciphertext in SEAL

Let's say I calulated addition or multiplication of 2 Ciphertexts and seved the result in a third one. If I want to perform additional mathematical operations on my result Ciphertext (destination Chipertext), is it advisable to use evaluator.relinearize() on it before doing so? Because if I understood it correctly, some operations on Ciphertext cause the result Ciphertext size to be larger than 2. If yes, then would this be a good approach for relinearizing one Ciphertext?

  • EvaluationKeys ev_keys;
  • int size = result.size();
  • keygen.generate_evaluation_keys(size - 2, ev_keys); // We need size - 2 ev_keys for performing this relinearization.
  • evaluator.relinearize(result, ev_keys);
Solution

  • Only Evaluator::multiply will increase the size of your ciphertext. Every ciphertext has size at least 2 (fresh encryptions have size 2) and multiplication of size a and b ciphertexts results in a ciphertext of size a+b-1. Thus, multiplying two ciphertext of size 2 you'll end up with a ciphertext of size 3. In almost all cases you'll want to relinearize at this point to bring the size back down to 2, as further operations on size 3 ciphertext can be significantly more computationally costly.

    There are some exceptions to this rule: say you want to compute the sum of many products. In this case you might want to relinearize only the final sum and not the individual summands, since computing sums of size 3 ciphertexts is still very fast.

    To make relinearization possible, the party who generates keys needs to also generate evaluation keys as follows:

    EvaluationKeys ev_keys;
keygen.generate_evaluation_keys(60, ev_keys);

    Later the evaluating party can use these as:

    evaluator.relinearize(result, ev_keys);

    Here I used 60 as the decomposition_bit_count in generate_evaluation_keys, which is the fastest and most often best choice. You should probably never use a int count parameter different from 1 (default) in generate_evaluation_keys. This is meant for use-cases where you let your ciphertexts grow in size beyond 3 and need to bring them down from e.g. size 4 or 5 down to 2.