ML-KEM implementation with preallocated reusable working memory

[kstzavertaylo]

Hello,

I implemented and evaluated ML-KEM using an approach in which working memory is allocated during key creation and subsequently reused by decapsulation operations.

Main characteristics of the implementation architecture:

1. Measured stack usage remains slightly above 1 KiB and is largely independent of the selected ML-KEM parameter set.

2. Encapsulation and decapsulation perform no runtime memory allocations. The required memory is allocated during key creation and subsequently reused until the key is destroyed.

3. Decapsulation uses a pool of reusable workspace slots to preserve concurrency without per-operation allocation.
The number of slots is selected during key creation according to the maximum number of concurrent decapsulation operations expected in the target environment.

4. The common implementation core is written in portable C11 with minimal reliance on environment-specific facilities.
Allocation, entropy generation, synchronization, error handling, and other environment-dependent functionality are isolated in separate port layers.
Ports are currently provided for Linux userspace, the Linux kernel, and FreeRTOS.

The implementation supports ML-KEM-512, ML-KEM-768, and ML-KEM-1024. It has been validated using NIST KAT vectors and additional functional and stress tests.
Timing-leakage testing was performed using dudect. Performance was compared with PQClean, with generally comparable throughput across the three parameter sets.

The main trade-off is a larger one-time allocation during key creation, retention of the preallocated workspace memory for the lifetime of the key, and greater internal complexity.
Rather than obtaining working memory separately for each operation, the implementation reserves it in advance and reuses it across all subsequent operations.
For a given level of concurrency, this does not necessarily increase the working-memory requirement; it changes its lifetime and moves memory acquisition out of the operational path.
The size of the initial allocation increases with the configured number of workspace slots.

I would be interested in the community’s view on the following questions:

1. Is this memory-management trade-off useful for constrained or allocation-sensitive environments, or is caller-provided per-operation workspace generally a preferable model?

2. Are there cryptographic, portability, or concurrency concerns specific to ML-KEM that should be considered when working memory is retained and reused for the lifetime of a key?

3. More broadly, is this implementation model suitable for ML-KEM and potentially useful for other PQC algorithms? What environments or use cases, if any, would benefit from such an approach?

The implementation, documentation, test results, and benchmark methodology are available in the v1.4.0 release:

https://github.com/kstzv/ml-kem/releases/tag/v1.4.0

Any technical feedback on the design and its trade-offs would be appreciated.

Best regards,
K. S. Zavertailo

[Becker, Hanno]

Hi,

Related: In mlkem-native (https://github.com/pq-code-package/mlkem-native) and mldsa-native (https://github.com/pq-code-package/mldsa-native), allocation is macro-configurable, allowing for stack, heap, or workspace allocation.

Best,

Hanno

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of kstzavertaylo <kstzav...@gmail.com>
Date: Tuesday, 11 August 2026 at 17:44
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXTERNAL] [pqc-forum] ML-KEM implementation with preallocated reusable working memory

CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/5bc03af4-6bce-4cda-ad4f-f7238beebcc2n%40list.nist.gov.

[kstzavertaylo]

Hi,

Yes, I am familiar with mlkem-native. My goal with this implementation was somewhat different: rather than providing different allocation strategies to choose from, I wanted to preserve several properties simultaneously — a small stack footprint, no allocations on the decapsulation path, and the ability to process two or more ciphertexts concurrently for the same key.

The intention was also to make the implementation suitable for environments that are sensitive to both stack usage and runtime allocations, without having to sacrifice concurrency to achieve that.

For that reason, the required working memory is allocated ahead of time and reused, with the amount of decapsulation concurrency determined when the key is created.

I also wanted to keep as much of the implementation as possible in portable C11 using only the standard library, leaving only a thin environment-specific porting layer.

Best,
Kst

середа, 12 серпня 2026 р. о 14:15:18 UTC+3 Becker, Hanno пише: