# 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, 2023 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, 2023 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, 2023 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, 2023 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, 2023 at 11:23