# Noise bound in FHE over the integers

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 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?

• 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'}$. – Radu Titiu Feb 3 '15 at 10:10

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

• 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^ρ – JongHyun Kim Jul 31 '14 at 22:11
• @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.) – D.W. Jul 31 '14 at 23:58
• Ok. I will modify my Question. – JongHyun Kim Aug 1 '14 at 0:40