[TLS] Re: WG Adoption Call for ML-KEM Post-Quantum Key Agreement for TLS 1.3

[Bas Westerbaan <[e-mail]>]

On Wed, Apr 16, 2025 at 10:15 AM Bellebaum, Thomas <
[e-mail]> wrote:

> > That’s easy to answer: “many of our members have very
> hardware-constrained PoS devices.” Is that okay?
>
> Some context:
>
> Kyber requires several KB of RAM space according to [1], figure 1:
>
> KG = KeyGen, E=Encaps, D=Decaps, H=Heap, S=Stack
>
> Alg       | KG(H) | KG(S) | E(H)  | E(S)  | D(H)  | D(S)
> ----------+-------+-------+-------+-------+-------+------
> Kyber1024 |13,480 |16,488 |10,736 |19,024 |10,768 |20,304
> Kyber512  |11,176 | 7,208 | 7,632 | 9,072 | 7,664 | 9,856
> Kyber768  |12,328 |11,304 | 9,104 |13,680 | 9,136 |14,784
>

This is misleading. There are many implementations of Kyber that require
much less memory. See eg [1] from 2019 where Kyber-512 only requires 2736
bytes.

By the way, for key agreement, between keygen and decapsulation, a client
only needs to keep around the private key seed (64 bytes).


> For comparison, [2] is an implementation of Curve25519 using no heap space.
> On an ATmega128, it uses 462 bytes of stack space for a curve
> multiplication.
>
> While these numbers are not comparable as is (C25519 does not include the
> KEM-Hash, Architectures are different, I am unconvinced that Kyber was
> fully optimized for this in [1]), the difference is striking enough to ask
> a follow up:
>
> Are there concrete devices/scenarios supporting ML-KEM + an application,
> but not ML-KEM + X25519 + an application, especially since the memory
> necessary to store two X25519 keys and a DH-KEM session key during the
> ML-KEM computations is 3*32 bytes?
>
> -- TBB
>

Best,

 Bas

[1] https://cryptojedi.org/papers/nttm4-20190513.pdf