2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$
    – Binou
    Commented Mar 13, 2019 at 6:58
  • 1
    $\begingroup$ 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). $\endgroup$
    – LeoDucas
    Commented Mar 13, 2019 at 20:26
  • $\begingroup$ 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}$... $\endgroup$
    – Binou
    Commented Mar 14, 2019 at 1:29
  • $\begingroup$ the answer to this comment was too long and I added it as an edit of the message. $\endgroup$
    – LeoDucas
    Commented Mar 14, 2019 at 8:15
  • $\begingroup$ 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. $\endgroup$
    – Binou
    Commented Mar 15, 2019 at 4:54

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.