3
$\begingroup$

From the LTV-FHE paper I find out that after every multiplication there must be a modulus switch to mitigate the noise in the resulting ciphertext, besides relinearization.

But, assuming the ciphertexts to be summed are the result of many operations and we have consumed many levels of the moduli ladder, that means that the room for noise is smaller. ( The assumption that the room for noise is getting smaller may be wrong, I haven't found any proof yet, is my personal observation.)

So, if we evaluate homomorphically many additions of ciphertexts like those aforementioned, should we use modulus switching to cut the noise before wrap around ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

First of all, I want to clarify that there is no relinearization involved in ciphertext multiplication.

Second, as discussed in the BGV paper, its not the ratio of noise to modulus size that matters but the absolute magnitude of noise is important and we should bring down the noise magnitude after each multiplication.

And finally comparing homomorphic addition to multiplication, the noise growth in multiplication is exponential whereas the noise growth in addition is atmost a single bit. Therefore we can perform multiple additions but not multiplications. Theoretically, you can compute a bound for maximum number of additions or multiplication before the noise wraps around the modulus, rendering the decryption unsuccessful.

I hope this helps you.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Adding an important detail: Parameters of FHE schemes may often be set so that it takes superpolynomial time to evaluate enough additions to pass the scheme's tolerated noise bound. (That is, for the sake of any polynomial time machine, the number of additions is effectively unbounded.) $\endgroup$
    – Daniel Apon
    Aug 19, 2016 at 7:09
  • $\begingroup$ Concretely: Set up ciphertexts so that addition increases magnitude of noise by (fixed) $poly(\lambda)$ (additively). Set noise threshold to $2^\lambda.$ $\endgroup$
    – Daniel Apon
    Aug 19, 2016 at 12:06

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.