I'm going through the FV scheme and SEAL and there are a couple of things I'm not understanding with respect to noise growth of relinearisation.

  • On page 8 they say to choose T so that the noise growth from relinearisation is similar to that of multiplication. Why do we want the noise growth to be size and not just as small as possible? On page 9 they follow up saying if they choose large T they'll get large relinearisation noise, but then all following relinearisations don't cause the noise to increase? How is this? I multiply c1*c2, relinearise, then multiply that by c3 and relinearise again, why wouldn't the noise increase?
  • On page 11, first paragraph after lemma 3, they mention they can ignore the noise from relinearisation because it's smaller than multiplication. Why can they ignore it? Isn't that making the bound on ||v_mul|| smaller than it should be (and possibly lead to a bad decryption)?
  • In the BFV basics example in SEAL, they show how relinearisation actually increases their noise budget compared to repetitive multiplication. Why is this? If we follow what the FV paper says, relinearisation should increase the noise, and therefore reduce the noise budget.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.