# Size of Fresh Ciphertext's Noise in FHE over the integers

I'm studying FHE over the Integer which is https://eprint.iacr.org/2009/616.pdf

In the remark 3.4, it says that the fresh ciphertexts have noise at most $2^{\rho'+2}$.

I don't know why that statement is true.

In my guess, the value $2^{\rho'+2}$ came from $m+2r$. But it cannot be strict proof of the statement.

Can anybody help me?

$c \leftarrow m + 2r + 2 \sum\limits_{i \in S} x_i \bmod x_0 = m + 2r + 2\sum\limits_{i \in S} (pq_i + r_i) + k(pq_0 + r_0)$ for some $k$.
When we do modular reduction by $p$, what remains is $m + 2r + 2\sum\limits_{i \in S} r_i + k r_0$. This (without $m$) is called the noise - as long as it doesn't wrap around $\bmod p$, decryption will succeed. So the term $2r + 2\sum\limits_{i \in S} r_i + k r_0$ is what they are referring to with "noise".
I do understand your confusion though - while $2r$ does seem to have the longest bitlength $\rho' + 2$, I'm not clear on why $2\sum\limits_{i \in S} r_i$ can't exceed this, as we have up to $\tau$ terms that we are adding.
• I think it works if you take the proposed set of parameters and develop the expression you found... $\tau = \gamma + \lambda$, thus, $\log \tau < 2 \log \gamma = 10\log \lambda$, thus, $|2\sum{r_i}| < \tau 2^\rho = \tau 2^\lambda = 2^{\lambda + \log \tau} < 2^{\lambda + 10\log\lambda}$. Now notice that $2^{\rho'} = 2^{2\lambda}$... Mar 14, 2020 at 14:44