2
$\begingroup$

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?

Improve this question
$\endgroup$
2
$\begingroup$

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!

Improve this answer
$\endgroup$
  • $\begingroup$ I agree with you. I think the authors didn't perfectly make this thesis. I could find some more errors in this thesis... $\endgroup$ – JongHyun Kim Aug 4 '14 at 10:15
  • $\begingroup$ 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}$... $\endgroup$ – Hilder Vitor Lima Pereira Mar 14 '20 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.