# Hardness of LWE

I was reading "TFHE Deep Dive" from Ilaria Chillotti, and I am a bit confused over the sample given in 31:08 In the above toy sample, isn't it possible to directly eliminate noise by shifting ciphertext by $$\Delta$$, then by Gaussian Elimination yielding plaintext?

In general, while intuitively original LWE hardness make sense (errors taken from $$D_{L,r}$$ with $$r\geq \eta_\epsilon(L)$$, so support of error cover then whole modulus), I don't really understand how are schemes keeping noise completely separate from plaintext (like above) secure, can't I just discard the noisy bits and do regular gaussian elimination ...?

This is probably a dumb question. Thanks for the reply :)

• Try to think better about what you mean by "discard the noisy bits"... Jan 31 at 15:05
• The noise can also be negative, no? The top part of the message would then be altered and truncating the bits would give the wrong data. Jan 31 at 23:55

If $$b = as + e$$ and the norm of $$e$$ is bounded by $$2^k$$, then zeroing the noisy bits means that you are computing $$u = b \bmod 2^k$$ and $$b' = b - u$$. Notice that the $$k$$ lowest bits of $$b'$$ are zero. But what you obtained is just $$b' = as + e - u$$. Also notice that since $$b$$ is random, $$u$$ is also so (although it is known).
• What I mean is to perform rescale over the entire ciphertext $(a,b)$, rather than the $b$ term only. A rescale homomorphically performs division and round to nearest element, hence removing the lower bits containing noise, leaving a valid encryption of zero with no noise. Having said that though, I am not really sure how to homomorphically perform division, aside from knowing CKKS being able to achieve it. Mar 15 at 5:24
• Zeroing the lowest bits takes values from $\mathbb{Z}_q$ and outputs values of $\mathbb{Z}_q$ again. Rescaling is different because it also reduces the modulus. That is, if you divide a ciphertext whose noise is $e$ by some $D$ that divides $q$, then you output a ciphertext with noise close to $e/D$ but modulus $q/D$. So the relative noise is essentially the same, i.e., $(e/D) / (q/D) = e / q$, thus the "security of both ciphertexts" is basically the same (remember that the hardness of LWE depends on the ration "norm of noise" over "ciphertext modulus"). Mar 15 at 9:22
• But if $|e|<\frac{D}{2}$, does that mean rescale lead to valid encryption with zero noise? since $(e/D)=0$ Mar 16 at 11:23