3
$\begingroup$

I was reading "TFHE Deep Dive" from Ilaria Chillotti, and I am a bit confused over the sample given in 31:08 enter image description here 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 :)

Improve this question
$\endgroup$
2
  • $\begingroup$ Try to think better about what you mean by "discard the noisy bits"... $\endgroup$
    – Hilder Vitor Lima Pereira
    Jan 31 at 15:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – JeremyKun
    Jan 31 at 23:55

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – xade93
    Mar 15 at 5:24
  • $\begingroup$ 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"). $\endgroup$
    – Hilder Vitor Lima Pereira
    Mar 15 at 9:22
  • $\begingroup$ But if $|e|<\frac{D}{2}$, does that mean rescale lead to valid encryption with zero noise? since $(e/D)=0$ $\endgroup$
    – xade93
    Mar 16 at 11:23
  • $\begingroup$ 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 to see the exact equations. $\endgroup$
    – Hilder Vitor Lima Pereira
    Mar 16 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.