In Algorithm 1 of paper “Revisiting Homomorphic Encryption for Finite Fields” during SwitchBasis step the vector Qk_{tensor} get vanishes (as switching from R_{p} to R_{q}).
As Qk is overflow error which comes from fast base extension. Thus, during SwitchBasis may be gamma correction or floating point instructions are used (as used in previous works). In my understanding SwitchBasis also produces some error but the noise bound computed in this paper are free from these noise.
Does this bound is tight ? Kindly correct my thinking if I’m wrong somewhere.
There were several grammatical errors/typos in your message. Let me rephrase your question to make sure I understand it correctly. When using fast basis extension (or also known as approximate basis switch), we get an extra overflow error. Why is this error not shown in Algorithm 1?
Because we remove this error in basis extension either using a floating-point technique (in the HPS variant and other variants derived from it) or gamma correction technique (in the BEHZ variant). When doing the scaling in BFV multiplication, some error can be tolerated.
Generally speaking, a small (rounding) error may appear when using the basis extension with a floating-point correction, but this error has a low probability and is small to have any practical effect. See the correctness discussions in An Improved RNS Variant of the BFV Homomorphic Encryption Scheme for more details. Hence it is safe to assume that the effect of these “secondary” errors is practically negligible.
