Open utterances-bot opened 4 months ago
Nice article! One minor nitpick: rounding the noisy plaintext is part of decryption (in fact, the hardest part!) and you treat it as part of decoding a plaintext.
If rounding were not part of decryption, then one could implement bootstrapping without all that blind rotate magic, because the first step in bootstrap is to homomorphically apply b - <a,s>
, a linear operation. Sec 5.2 of https://eprint.iacr.org/2021/1402 explains this in a bit more detail.
Thanks!
I completely agree that it is possible to homomorphically evaluate b - <a,s>
much more easily using homomorphic addition and multiplication. However, wouldn't we still need some sort of blind rotate magic to bound the output error?
Also, thanks for the link to that article - it looks great!
Yes, what I'm saying is your LWE decryption implementation does not round, so it is not technically the complete decryption operation. Putting the rounding as part of decoding is slightly misleading, in my opinion, because of this relationship to homomorphic decryption, which must include that step.
But it is a very minor quibble.
That makes sense - thanks!
http://localhost:4000/blog/2024/01/03/fully-homomorphic-encryption