Score:0

Two problem about noise management of BFV

gd flag

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?

Score:3
tn flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.