Which Operations can be followed Multiplication w/o Relinearization?

FHE Questions
1

I have a general question concerning multiplication w/o relinearization, when using BFV, BGV or CKKS. My understanding is:

Let SK denote the secret key. If I have two ciphertexts C^{(1)} = (c^{(1)}_0, c^{(1)}_1) and C^{(2)} = (c^{(2)}_0, c^{(2)}_1) encrypting m^{(1)} and m^{(2)} respectively (that is, c^{(i)}_0 + c^{(i)}_1 \cdot SK = d \cdot m^{(i)} + e, where d is a factor which might equal 1 in case of BGV, and e is a small error), than homomorphic multiplication of C^{(0)} and C^{(1)} w/o relinearization yields a 3-component ciphertext C = (c_0, c_1, c_2) with c_0 + c_1 \cdot SK + c_2 \cdot SK^2 = d^2 \cdot m^{(1)} \cdot m^{(2)} + \text{some error}.

  1. Looking on these equations, I think it should not be a problem to evaluate homomorphic additions on 3-component ciphertexts. Even mixing 2-component and 3-component ciphertext should work (by extending the 2-component ciphertext with an additional 0). Is this correct?

  2. Maybe I can even do a subsequent multiplication, which would further blow up the ciphertext, but may be ok in principal as long as the error does not grow to much. Is this correct? Or might this be useless as the further blown up ciphertext could never be decrypted / relinearized anymore?

  3. The most relevant question for my application in mind: Can I perform homomorphic rotations on a 3-component ciphertext? I have already experimented a bit and got wrong results, but I am not sure if this was due to the chosen parameters or if this is generally not possible.

Thank you very much in advance!

2

Theoretically speaking, any operations can be performed on ciphertexts resulting from homomorphic multiplication w/o relinearization. The main issue is that the size of the ciphertext grows from 2 polynomials to 3 (for SK^2), 4 (for SK^3), and so on. To support relinearization for degrees of SK that are higher than 2, SetMaxRelinSkDeg should be set to the maximum degree (it is 2 by default). Hence, the answers to 1 and 2 are “YES”.

For rotations, we do not support quadratic and higher degrees as we often deal with multiple rotation keys, one per each rotation index (in contrast to 1 key for SK^2 relinearization). The memory requirement would be too high in this case. So the current solution is to relinearize the ciphertext to 2 polynomials (linear form) before performing any rotations on it.

3

Thank you very much for your explanations!