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

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

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/