I have stuck in two problems when understanding the noise management of BFV scheme, and I don't have any idea about the two problem, help me please.

Problem 1:
In the Lemma 3 , the paper demonstrates that the norm of the noise after multiplying two ciphertexts $ct_0$ and $ct_1$ is $\left \|v_{mul}\right\|$=$E\cdot\delta_R\cdot(\delta_R+1.25)+E_{Relin}$, and I think the norm of $v_{mul}$ should be the the sum of $v_3$'s norm in Lemma 2 and $E_{Relin}$ in the Relinearisation step. The norm of $v_3$ in Lemma 2 is $2\cdot\delta_R\cdot t\cdot E\cdot (\delta_R \cdot \left \|s\right\|+1)+2\cdot t^{2}\cdot\delta_R^2\cdot(\left \|s\right\|+1)^2$, and it has a significant gap with the norm of $\left \|v_{mul}\right\|$ with $E_{Relin}$ removed. I am very confused with the gap, do you know why?

Problem 2:
The paper gives a noise size roughly after L levels of multiplications in the content between Lemma 2 and Theorem 1, it's $2\cdot B\cdot \delta_R^{2L+1}\cdot t^L$, and it seems that it can't be derived from Lemma 3. Do you know how the noise size comes?


1 Answer 1


Problem 2 first. If you use $E=2*\delta_R*B$ as an initial noise and you perform $L$ multiplications (using the same ciphertext), then you multiply (see Lemma 2) the noise $E$ each time by $t\cdot \delta_R(\delta_R+1.25)$, ignoring the relinearization error as in the paper. In total, you have $E\cdot t^L \cdot \delta_R^L (\delta_R + 1)^L$ afterwards. Now, they estimated $(\delta_R+1)^L \approx \delta_R^L$, which yields the claim.

Problem 1 seems a bit trickier. For sure they assumed $\| s \| = 1$. Since in Lemma 3 $t$ doesn't show up, probably they assumed it to be small, too (which it should be because of the statement in Lemma 2). The crucial observation is to ask where the $(\delta_R+1.25)$ comes from. I'm not 100% sure, but I think you'll find the answer in the discussion above Lemma 2, especially $\| r_a \| < (\delta_R + 1)^2/4$ looks suspicious in that matter.


Your Answer

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

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