Search code examples
c++encryptionseal

Perform Addition on a Product using the S.E.A.L. Library

I am trying to perform an operation that is of the form: (A * B) + C. The multiplication works fine, as all the numbers have the same scale at that point, but the product of A * B has a different scale than C. It makes sense that multiplication would change the scale, but I was wondering if there was a way to perform an operation like this using the SEAL library.

Environment information:

  1. Language: C++
  2. Encryption Scheme: CKKS
  3. Small encoded doubles (eg. 0.4531)
  4. Scale used for encoding: pow(2.0, 60) like the example

Thank you in advance and let me know if further information is needed.

Solution

  • There are multiple ways of getting this to work. For example, suppose ciphertexts A, B, C all have the same scale Z. Then A * B will have scale Z^2. At this point you should also relinearize A * B unless you have a strong reason not to.

    To compute A * B + C, you could for instance:

    • re-encode C (if you have the plaintext) with scale Z^2 and use that instead;
    • use multiply_plain to multiply C with a scalar 1.0 plaintext with scale Z to increase the scale to Z^2 but keep the value the same (there is an overload for CKKSEncoder::encode for this);
    • rescale A * B first so it has scale Z^2/q_k where q_k is the last prime in the coeff_modulus. Now, you could re-encode C to have scale exactly Z^2/q_k (if you have the plaintext), or multiply C with a scalar 1.0 plaintext as explained above to change the scale to exactly Z^2/q_k;
    • if Z is close to q_k so that Z^2/q_k ~ Z, then after rescaling you might just be able to use double &Ciphertext::scale() to set the scale of A * B to exactly C.scale() at the cost of a small multiplicative error ~ Z/q_k. For example, instead of scale 2^60 for A, B, C you could use static_cast<double>(parms.coeff_modulus().back()). Then Z^2/q_k = Z (exactly) and the addition works immediately without any scale switching. Of course, this doesn't work so well anymore after a second multiply+rescale as the second to last prime can no longer be equal to Z (all primes in coeff_modulus must be distinct).