Having a homomorphic encryption scheme like BGV or LTV-FHE at some point it is possible in the homomorphic evaluation to deal with ciphertexts that are encrypted with respect to different moduli.

For the chosen scheme we have a ladder of decreasing moduli $q_0 > ... > q_{t-1}$. If there is a ciphertext $c_1$ w.r.t $R_{q_2}$ and another ciphertext $c_2$ w.r.t to $R_{q_4}$, the first ciphertext should be "switched" into the ring $R_{q_4}$ and only then the homomorphic computation could be done ?

Or maybe this situation should be avoided ? Then, if this is the case, how about computation represented as an unbalanced tree of multiplications? At some point there will be a need to multiply two ciphertexts encrypted in different subrings.


1 Answer 1


The problem is that operations between such $c_1$ and $c_2$ are not even defined. You have to reduce the coefficients of the resulting polynomial modulus either $q_2$ or $q_4$, so, you have to switch one of them.

Switch $c_2$ into $R_{q_2}$ would work as well, but since it would increase the noise in $c_2$, it is smarter to switch $c_1$ into $R_{q_4}$ (which gives you meaningful operations and also decrease the $c_1$'s noise).

I think the only way to avoid this switching is to treat both the polynomials as elements of $R$ and check if the coefficients of the resultant polynomials are not greater than $q_4$, because this means that no reduction would be done in the coefficients if operations were done in $R_{q_4}$ and so the resultant polynomial is a valid ciphertext in $R_{q_4}$ and in $R_{q_2}$.

Anyway, the modulus switching operations is not expensive, and it also reduces the noise, so, I don't see advantages in avoiding to do them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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