Noise bound in FHE over the integers

Question

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?

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

and

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