Hardness of LWE

xade93

1/30/24, 2:30 AM

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 :)

171

1 + 2

homomorphic-encryption

lattice-crypto

lwe

ring-lwe

Hilder Vitor Lima Pereira

1/31/24, 3:05 PM

Try to think better about what you mean by "discard the noisy bits"...

JeremyKun

1/31/24, 11:55 PM

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.

Score:4

Crypto

Hilder Vitor Lima Pereira

2/1/24, 2:51 PM

Discarding the noisy bits just means that you are "overwriting" that noise with new noise, essentially.

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).

Therefore the noise is always there anyway.

+ 4

xade93

3/15/24, 5:24 AM

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.

Hilder Vitor Lima Pereira

3/15/24, 9:22 AM

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").

xade93

3/16/24, 11:23 AM

But if $|e|<\frac{D}{2}$, does that mean rescale lead to valid encryption with zero noise? since $(e/D)=0$

Hilder Vitor Lima Pereira

3/16/24, 3:29 PM

e/D is not zero. Round(e/D) would be zero in this case, but you don't round the error when you round the ciphertext. Moreover, there are actually other noise terms included by the rounding. I suggest that you check my answer [here](https://crypto.stackexchange.com/questions/66186) to see the exact equations.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Hardness of LWE

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.