[markschultz]

I wrote up an introduction to a (severely unoptimized for pedagogical purposes) version of FrodoKEM

https://mark-schultz.github.io/nist-standard-out/

It's the same base scheme as Saber/Kyber, although as Saber/Kyber are over algebraically structured lattices they are significantly more efficient.

[sbf501]

Thanks for taking the time to write this up. But, woof, it's a bit more than ELI5. :) The python code makes it a little more clear since I'm not familiar with some of the notation. However, it does seem kind of magic that 'e' is derived during the encryption and then sort of vanishes. I also don't quite get the bounded vs uniform vector sampling calls (one for s and the other for chi). But this at least greases the wheels so to speak, so thanks!

[markschultz]

Thanks for the feedback! Roughly speaking, that all has to do with making e vanish later, so perhaps I need to revisit that section.

Quickly (cause I probably won't for a few days), (q//2)m can be seen as a form of error correction. You can check (either pen+paper or programmatically) that, provided |e| < q/4, if noisy_m = (q//2) m + e, then round(noisy_m / (q/4)) = m. So e vanishes because it is bounded (not uniform), + we encode m as (q//2)*m (i.e. in the "most significant bits" of the number).