Why the refresh (modulus and key switching) is required in BGV after addition?

Question

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}$.

Answer 1

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/