[CFRG] Re: Progressing NTRUPrime/Classic McEliece drafts

[John Mattsson <[e-mail]>]

Martin Thompson wrote:
>With a 240 byte ciphertext (I had trouble finding a specific value, so this might be incorrect), that's quite a lot smaller than ML-KEM-768.  The ~800 bytes of saving per message means that you need to clear ~1200 messages for each public key transfer before the overall transfer cost is neutral.

Just hours before you sent this, I made a graph illustrating the overhead of the static encapsulation key and ciphertexts in ML-KEM and Classic McEliece as a function of the number of encapsulations. When the public key is provisioned in-band, I think Classic McEliece has less overhead than ML-KEM at the same security level after just a few hundred encapsulations, see Figure 1 of [1]. Also, users might be comfortable with a lower security category for Classic McEliece compared to ML-KEM, given its attack complexity has remained stable for decades.

>But the likelihood that messages fit in a single packet is a huge gain that has value far beyond what a simple tally might suggest.
That the small ciphertexts avoid fragmentation is a great reflection, I agree that is very important. I added that to my paper [1] before submitting to NIST.

Cheers,
John

[1] ML-KEM is Great! What’s Missing?
https://emanjon.github.io/Publications/ML-KEM%20is%20Great!%20What's%20Missing.pdf