1
$\begingroup$

I am reading the BGV paper. On page 18, after addition, the protocol will also refresh (modulus and key switching), may I ask why is this required? It seems to me that I can still use the same secret to decrypt the added ciphertexts.

  • $\text{FHE.Add}(pk, c_1, c_2$): Takes two ciphertexts encrypted under the same $s_j$. (If needed, use $\text{FHE.Refresh}$ (below) to make it so.) Set $c_3 \leftarrow c_1 + c_2 \mod q_j$. Interpret $c_3$ as a ciphertext under $s'_j$ ($s'_j$'s coefficients include all of $s_j$'s since $s'_j = s_j \otimes s_j$ and $s'_j$'s first coefficient is 1) and output:

    $$c_4 \leftarrow \text{FHE.Refresh}(c_3, \tau_{s'_j \rightarrow s_{j-1}}, q_j, q_{j-1})$$

  • $\text{FHE.Mult}(pk, c_1, c_2$): Takes two ciphertexts encrypted under the same $s_j$. (If needed, use $\text{FHE.Refresh}$ (below) to make it so.) First, multiply: the new ciphertext, under the secret key $s'_j = s_j \otimes s_j$, is the coefficient vector $c_3$ of the linear equation $L_{c1,c2}^{long}(x \otimes x)$. Then, output:

    $$c_4 \leftarrow \text{FHE.Refresh}(c_3, \tau_{s'_j \rightarrow s_{j-1}}, q_j, q_{j-1})$$

  • $\text{FHE.Refresh}(c, \tau_{s'_j \rightarrow s_{j-1}}, q_j, q_{j-1}$): Takes a ciphertext encrypted under $s'_j$, the auxiliary information $\tau_{s'_j \rightarrow s_{j-1}}$ to facilitate key switching, and the current and next moduli $q_j$ and $q_{j-1}$. Do the following:

    1. Switch Keys: Set $c_1 \leftarrow \text{SwitchKey}(\tau_{s'_j \rightarrow s_{j-1}}, c, q_j)$, a ciphertext under the key $s_{j-1}$ for modulus $q_j$.
    2. Switch Moduli: Set $c_2 \leftarrow \text{Scale}(c_1, q_j, q_{j-1}, 2)$, a ciphertext under the key $s_{j-1}$ for modulus $q_{j-1}$.
$\endgroup$
0

1 Answer 1

0
$\begingroup$

The sentence says almost all;

  • If needed, use $\text{FHE.Refresh}$

The homomorphic operations in BGV increase the noise, so eventually, your noise should be handled with $\text{FHE.Refresh}$

The noise increase in addition is small, compared to the mostly quadratic multiplication. The paper clearly states this (page 4);

Addition of two ciphertexts with noise at most $B$ results in a ciphertext with noise at most $2B$, whereas multiplication results in a noise as large as $B^2$.

So after around $\log_2 B$ additions you will have the same noise level as in one multiplication.

Keep in mind that this paper also gives a new noise-management technique to reduce it without bootstrapping/

$\endgroup$

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.