Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
Let's look at the ciphertext:
$ 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.
Sorry I couldn't answer your question in full!
