A toy implementation of ML-KEM algorithm?

[tomato42]

So, to continue my insistence that this library is a very good learning resource I was thinking of including a complete toy example variant of ML-KEM: one that uses and encrypts only 1 byte values at a time (i.e. one that uses just 8-th degree polynomials).

Would you be ok accepting such code?

Alfred Menezes has published a series of lectures where he uses an implementation like that (the nice thing about 8-th degree polynomials is that NTT works for them too).

[GiacomoPope]

yeah this sounds great and if the maths code I designed was abstract enough it should be fairly easy to implement on top of what we have :)

[tomato42]

the downside is that we would have to parametrise more of the ml-kem code; so that outputs of stuff like hash functions is also defined by parameters...

[GiacomoPope]

we could make a ml_kem_toy directory with the code which then calls a specific class make in polynomials etc? Hard to know what's best here

[tomato42]

that would lead to a lot of code duplication, that's why I was trying to avoid it...

but maybe a base ml_kem class that has the stuff common between the regular ml-kem and the ml-kem-toy, and have stuff like hash functions in the concrete instantiations...

[GiacomoPope]

ideally it would be nice for ML-KEM to "work" with any supplied polynomial ring and module providing the available API is correct

[tomato42]

yes, but that requires the parameters to also include polynomial ring and module definitions; if you're ok moving them to those parameters:

kyber-py/src/kyber_py/ml_kem/default_parameters.py

Line 14 in 29afef2

"ML512": {"k": 2, "eta_1": 3, "eta_2": 2, "du": 10, "dv": 4},

then it should be doable

[GiacomoPope]

yeah i think we can do it, it's a little redundant in the sense that all "serious" implementations will have the same n but we can still put it in there to allow for the n value?