# Standard deviation of gaussian noise in FHEW scheme

I've got two questions regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second.

First, the final error of a ciphertext after the refresh procedure is stated as following a gaussian of standard deviation:

$$\beta = \sqrt{\dfrac{q^2}{Q^2}\left( \zeta^2 \cdot \dfrac{B_{r}^2}{12} \cdot nd_r\cdot \dfrac{q}{2} \cdot 2Nd' + \sigma^2Nd_{ks}\right) + \dfrac{\|\mathbf{s}\|^2+1}{12}}$$

Then, after giving their chosen parameters they conclude that $$\beta = 6.94$$. I don't understand where this result comes from. Even if we ignore the (positive) first term in the square root, as $$\|s\| \leq n/2$$ (with $$n=500$$ in the parameters), the standard deviation $$\beta$$ should be way bigger than $$6.94$$... Where does this result come from?

Second, they then say that the probability of error per homomorphic NAND is $$p = 1 - erf(r/\sqrt{2})$$ where $$r = \dfrac{q/8}{\sqrt{2}\beta}$$. I know that $$p$$ is the probability to get a sample outside of the interval $$[-r;r]$$, but I don't get why they set $$r$$ that way. What does it represent?

Apologies for seeing this question just now. For your first question, well, there seems to be a typo: I should have written $$\|s\|^2 \leq n/2$$, and then we have $$\sqrt{(\|s\|^2 +1) /12 } = \sqrt{251/12} \approx 4.57$$.

Now, we take 2 ciphertext with LWE error of std-deviation $$\beta$$, and sum them. Assuming independence the std-dev of the sum of the errors is $$\sqrt 2 \beta$$. For correctness, we need this sum of errors to be less than $$q/8$$ (Here, to save every last bit, we relax the naive condition stated in Lemma 7, and directly bound the sum $$q/8 + |e_0 + e_1|$$ by $$q/4$$ rather than bounding $$e_0$$ and $$e_1$$).

answer to comment on decreasing error via swapping KeySwitch and $$\textsf{HomNAND}$$

Just for the sake of this explanation, let me lie about the actual noise propagation, and assume that each operation HN and KS just add a constant to the quantity of noise, denoted $$h$$ and $$k$$.

The easy to describe scheme'' does $$\textsf{HomNAND}(KS(X_1), KS(X_2))$$, which leads to an error of the form $$(x_1 + k) + (x_2 + k) + h = x_1 + x_2 + h + 2k$$.

The better but less easy to describe scheme'' does $$KS(\textsf{HomNAND}(X1, X_2))$$which leads to and error $$(x_1+x_2+h) + k$$. That is one ks less.

It turns out that even with the actual formula, we also gain a little bit on the final error with this trick.

• May I ask a last question? How do you bring down the final probability of error from $2^{-31}$ to $2^{-45}? Thank you for all your support – Binou Mar 13 '19 at 6:58 • By doing the HomNAND before Keyswitch, you only pay for the extra noise of a KeySwitch once (on the resulting ciphertext) rather than twice (on both ciphertexts). – LeoDucas Mar 13 '19 at 20:26 • But isn't it what you already did in the above formula of$\beta$? The error of Key Switching is$\sqrt{\alpha^2 + N d_{ks}\sigma^2}$with$\alpha$the error of the resulting ciphertext. And this gives us a final error probability of$2^{-31}$... – Binou Mar 14 '19 at 1:29 • the answer to this comment was too long and I added it as an edit of the message. – LeoDucas Mar 14 '19 at 8:15 • But hasn't this trick already been used in the formula of$\beta$? (hence giving a final parameter of$6.94$and probability of error around$2^{-31}$) In the sense that we get first the error of the accumulator$\alpha_1 = \zeta^2 \cdot \dfrac{B_g^2}{12} \cdot n d_r \cdot \dfrac{q}{2} \cdot 2 N d'$, then we compute the error from key switching$\alpha_2 = \sqrt{\alpha_{1}^2 + \sigma^2 N d_{ks}}$, and finally the one from mod switching$err(\mathbf{c}) = \sqrt{\dfrac{q^2}{Q^2} \alpha_{2}^2 + \dfrac{\| \mathbf{s} \| +1}{12}}\$ ? I'm probably wrong but for me the trick has already been used here. – Binou Mar 15 '19 at 4:54