I'm studying the paper Fully Homomorphic Encryption over the Integers by Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan.

I have questions about the proof of Lemma A.1.

In page 6, the element of public key is in the form of $x=pq+r$ and the encryption is $$ c← [m+2r+2\sum x_i]_{x_0} $$

But in the proof of Lemma A.1., the public key is $x=pq+2r$ and the encryption is $$ c← [m+2r+\sum x_i]_{x_0} $$

This problem made me confused. I tried to proof with first definition, but I encounter with another problem. When I follow the same flow of the proof with first definition, I reached that the noise term is $$(m+2r+k*r_0+ \sum 2r_i )$$ What I need to next is to get the upper bound of a $|m+2r+k\cdot r_0+ \sum 2r_i|$. So I got $$|m+2r+k*r_0+ \sum 2r_i| \leq m+2\cdot2^{\rho\prime} + \tau \cdot 2^{\rho}+\tau \cdot 2^{\rho} =m+2\cdot2^{\rho\prime} +2 \tau2^{\rho}$$

If the definition of permitted circuit in this thesis is correct, at least $$m+2\cdot2^{\rho\prime} +2 \tau2^{\rho} \leq 2^{\rho \prime +2}$$ should be satisfied.

Can anybody help to get upper bound of noise?

Original question

I'm reading https://eprint.iacr.org/2009/616.pdf

I am reading the proof of Lemma A.1 which is in page 21.

In the page 22, the thesis tells that the noise is at most $(4\tau + 3)2^\rho < \tau2^{ \rho+3}$.

But I cannot follow the inequality.

Could you guys help me to understand the proof of Lemma A.1?

  • $\begingroup$ Has someone managed to prove the estimation of $|m+2b|$? I don't even see why $|k| \leq \tau$. And even if this were true, I dont see how one can reach $(4\tau+3)2^\rho$ following JongHyun Kim's estimation, since we would have to bound the term containing $2^{\rho'}$. $\endgroup$
    – Radu Titiu
    Feb 3, 2015 at 10:10

1 Answer 1


Just expand it out. You get $4\tau \cdot 2^\rho + 3 \cdot 2^\rho$. Then,

$\tau \cdot 4 \cdot 2^\rho = \tau \cdot 2^2 \cdot 2^\rho = \tau \cdot 2^{\rho + 2}$


$3\cdot 2^\rho < 4 \cdot 2^\rho = 2^{\rho+2}$.

Put it back together,

$\tau \cdot 2^{\rho + 2} + 2^{\rho + 2} < \tau (2^{\rho + 2}+2^{\rho + 2}) = \tau 2^{\rho+3}$

  • $\begingroup$ Oh, Actually, I fail to achieve (4τ+3)2^ρ. the noise is m+2r+k*r_0+sigma(2r_i). When we use triangle inequality, 2r term becomes 2*2^ρ'. the point is that i cannot change 2*2^ρ' terms into some polynomials of 2^ρ $\endgroup$ Jul 31, 2014 at 22:11
  • 1
    $\begingroup$ @JongHyunKim, please don't use comments to ask a new question. Comments should only be used to help the author of the answer improve their answer. (This is not a discussion forum; see the faq for more details on how to use this site.) $\endgroup$
    – D.W.
    Jul 31, 2014 at 23:58
  • $\begingroup$ Ok. I will modify my Question. $\endgroup$ Aug 1, 2014 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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