Hi,
I've now merge Daiki's ML-KEM implementation, see https://git.lysator.liu.se/nettle/nettle/-/merge_requests/67.
I think there's some further changes I think I'd like to do before release:
1. Add more randomized tests, and add assert_maybe for some of the invariants, in particular for arithmetics.
2. Probably remove the ml_kem_params from the api, and instead use separate functions for ML-KEM 768 and ML-KEM 1024.
3. Add functions exposing structs for expanded keys. To avoid having to expand them over and over again if using the same key repeatedly. And for all-in-one functions, these structs could also be used as the types for needed scratch space, to make things a bit more type/alignment safe, and have a natural way to allocate needed storage without the _itch functions.
Should then be done in a consistent way also for sntrup. (The reason sntrup api doesn't have any itch function is that its expanded keys are smaller, and it's more reasonable to just allocate them on the stack).
4. Micro optimize various internals.
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
Hi,
I've now merge Daiki's ML-KEM implementation, see https://git.lysator.liu.se/nettle/nettle/-/merge_requests/67.
I think there's some further changes I think I'd like to do before release:
I've started to look into this, since I want to have an API i'm happy with prior to release.
- Add more randomized tests, and add assert_maybe for some of the invariants, in particular for arithmetics.
Partly done, at least some more asserts.
- Probably remove the ml_kem_params from the api, and instead use separate functions for ML-KEM 768 and ML-KEM 1024.
I've added specific functions in the most simple way on the branch refactor-ml-kem, but not yet un-exported the ml_kem params things.
- Add functions exposing structs for expanded keys. To avoid having to expand them over and over again if using the same key repeatedly. And for all-in-one functions, these structs could also be used as the types for needed scratch space,
When looking at this, I'm also looking at use of scratch space generally. Some notes...
For the lower-level primitives, the public key is a matrix A and a vector t, and the private key is a vector s. The "scalars" (i.e., an individual element of a matrix or vector) are polynomials mod (Q, X^256+1), represented as 256 uint16_t values.
So for ml-kem-768, the dimension is 3, and we have
A: 3x3x256 uint16_t values (generated from small public seed) t: 3x256 values s: 3x256 values
If we start with key generation, these values are currently all allocated from the provided scratch space (and only encoded versions of s and t are returned to caller). It also uses scratch space for a temporary noise vector e, for a total of 4608 values or 9 KiB. And there's probably another KiB or two allocated on the stack.
It would make sense to me to return A, t and s (the expanded public and private keys), and let functions above deal with encoding. And not encode and decode repeatedly as the same key is used multiple times. The spec hints that at least A can be cached in this way.
Another observation is that need for scratch space can be generally reduced by not computing and storing values long before they are needed. The A matrix is used for one matrix x vector multiplication, A * s. If s is generated upfront, it's sufficient to compute one row of A at a time or even a single scalar element at a time). Similarly, noice vector e could be generated and applied one element at a time.
If we do A row-wise, scratch space is then reduced to 2560 values or 5 KiB. If we do A element-wise, we would save one more KiB. (And relative saving would be larger for ml-kem-1024, where dimension is 4 rather than 3). Maybe still a bit large to unconditionally allocate on the stack, but if we store A, t and s in output areas, I think remaining temporary storage could go in the stack and itch/scratch could be eliminated.
Encapsulation uses a slightly different matrix x vector multiplication, A^T * y, so here it would be natural to generate A one column at a time.
On the other hand, top-level decapsulation uses both low-level decapsulation and encapsulation, so it needs A twice. Here it seems desirable to have all of A allocated in memory (passed in by caller, or generated once from the public seed). So then there's a consistency argument against generating A incrementally in the other functions.
For the encapsulation operation, one could also consider using the output ciphertext area for temporary storage, but it's relatively small so maybe not worth it.
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
- Probably remove the ml_kem_params from the api, and instead use separate functions for ML-KEM 768 and ML-KEM 1024.
I've added specific functions in the most simple way on the branch refactor-ml-kem, but not yet un-exported the ml_kem params things.
I've now merged the changes on the refactor-ml-kem branch. Deletes the generic api (and makes the ml_kem_params struct completely internal). I've also done a couple of optimization, with speedup of 30%-50% when benchmarking on x86_64.
- Add functions exposing structs for expanded keys. To avoid having to expand them over and over again if using the same key repeatedly. And for all-in-one functions, these structs could also be used as the types for needed scratch space,
After looking a bit closer, I'm not sure this is a good idea. We'll see.
[ ... key generation ...] Another observation is that need for scratch space can be generally reduced by not computing and storing values long before they are needed. The A matrix is used for one matrix x vector multiplication, A * s. If s is generated upfront, it's sufficient to compute one row of A at a time or even a single scalar element at a time). Similarly, noice vector e could be generated and applied one element at a time.
[...]
Encapsulation uses a slightly different matrix x vector multiplication, A^T * y, so here it would be natural to generate A one column at a time.
On the other hand, top-level decapsulation uses both low-level decapsulation and encapsulation, so it needs A twice.
The last sentence seems wrong, low-level decapsulation (inner_decrypt) doesn't use the matrix A at all.
So for the three top-level functions generate, encap and decap, all of them use A only once, and each element of A only once. So it should be straight forward to generate them one at a time. In principle, it should work fine to generate only 2 (out of 256) uint16_t coeffients at a time, but I suspect that going that far would come with a measurable performance penalty.
Regards, /Niels
On Mon, Sep 21, 2026, 8:21 PM Niels Möller nisse@lysator.liu.se wrote:
Niels Möller nisse@lysator.liu.se writes:
- Probably remove the ml_kem_params from the api, and instead use separate functions for ML-KEM 768 and ML-KEM 1024.
I've added specific functions in the most simple way on the branch refactor-ml-kem, but not yet un-exported the ml_kem params things.
I've now merged the changes on the refactor-ml-kem branch. Deletes the generic api (and makes the ml_kem_params struct completely internal). I've also done a couple of optimization, with speedup of 30%-50% when benchmarking on x86_64.
I think the implementation is already fast enough plus the optimizations are not on the hot path so it doesn't contribute much to the overall performance. Also, the new changes haven't been run yet on CI which keeps the other MRs open until this one closed.
- Add functions exposing structs for expanded keys. To avoid having to expand them over and over again if using the same key repeatedly. And for all-in-one functions, these structs could also be used as the types for needed scratch space,
After looking a bit closer, I'm not sure this is a good idea. We'll see.
I ran the changes on different CI jobs and the pattern passes successfully each time for the entire pipeline. One needs to trigger the CI first to decide.
[ ... key generation ...] Another observation is that need for scratch space can be generally reduced by not computing and storing values long before they are needed. The A matrix is used for one matrix x vector multiplication, A * s. If s is generated upfront, it's sufficient to compute one row of A at a time or even a single scalar element at a time). Similarly, noice vector e could be generated and applied one element at a time.
[...]
Encapsulation uses a slightly different matrix x vector multiplication, A^T * y, so here it would be natural to generate A one column at a time.
On the other hand, top-level decapsulation uses both low-level decapsulation and encapsulation, so it needs A twice.
The last sentence seems wrong, low-level decapsulation (inner_decrypt) doesn't use the matrix A at all.
You are looking at this very closely, but there is a subtle structural detail in how ml-kem handles its keys that changes how often matrix A actually needs to be generated. in some optimized implementations, decaps doesn't use the matrix A but in this case it does need A twice without considering the initial run. The sentence is correct as it stands.
So for the three top-level functions generate, encap and decap, all of them use A only once, and each element of A only once. So it should be straight forward to generate them one at a time. In principle, it should work fine to generate only 2 (out of 256) uint16_t coeffients at a time, but I suspect that going that far would come with a measurable performance penalty.
the caller appears to ignore the "performance penalty" since it's no longer an issue on modern devices. Running those parameters on non constrained environment is no brainer for developers as long they are serious about having one clean API.
best regards, Mamoun
Regards, /Niels
-- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-leave@lists.lysator.liu.se
On Mon, Sep 21, 2026 at 8:21 PM Niels Möller nisse@lysator.liu.se wrote:
Niels Möller nisse@lysator.liu.se writes:
- Probably remove the ml_kem_params from the api, and instead use separate functions for ML-KEM 768 and ML-KEM 1024.
I've added specific functions in the most simple way on the branch refactor-ml-kem, but not yet un-exported the ml_kem params things.
I've now merged the changes on the refactor-ml-kem branch. Deletes the generic api (and makes the ml_kem_params struct completely internal). I've also done a couple of optimization, with speedup of 30%-50% when benchmarking on x86_64.
I'm trying to understand the optimization logic here to see if there is a balance we can achieve. What specific speedup do you intend to target?
best regards, Mamoun
- Add functions exposing structs for expanded keys. To avoid having to expand them over and over again if using the same key repeatedly. And for all-in-one functions, these structs could also be used as the types for needed scratch space,
After looking a bit closer, I'm not sure this is a good idea. We'll see.
[ ... key generation ...] Another observation is that need for scratch space can be generally reduced by not computing and storing values long before they are needed. The A matrix is used for one matrix x vector multiplication, A * s. If s is generated upfront, it's sufficient to compute one row of A at a time or even a single scalar element at a time). Similarly, noice vector e could be generated and applied one element at a time.
[...]
Encapsulation uses a slightly different matrix x vector multiplication, A^T * y, so here it would be natural to generate A one column at a time.
On the other hand, top-level decapsulation uses both low-level decapsulation and encapsulation, so it needs A twice.
The last sentence seems wrong, low-level decapsulation (inner_decrypt) doesn't use the matrix A at all.
So for the three top-level functions generate, encap and decap, all of them use A only once, and each element of A only once. So it should be straight forward to generate them one at a time. In principle, it should work fine to generate only 2 (out of 256) uint16_t coeffients at a time, but I suspect that going that far would come with a measurable performance penalty.
Regards, /Niels
-- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-leave@lists.lysator.liu.se
nettle-bugs@lists.lysator.liu.se
-
Maamoun TK -
Niels Möller