[CFRG] Re: Progressing NTRUPrime/Classic McEliece drafts

[Martin Thomson <[e-mail]>]

On Mon, Jan 27, 2025, at 20:02, Thom Wiggers wrote:
> For Classic McEliece, I think it would be helpful if people come 
> forward with concrete applications in which they're actually 
> wanting/trying to deploy Classic McEliece.

I think that it would be very useful to have McEliece available for both Oblivious HTTP and (maybe) ECH.  We have a few cases where the number of times that public keys transit the network are far fewer than the number of ciphertexts.  Obviously, a hybrid with X25519 is probably where I'd want to go with that.

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.  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.

I mentioned ECH, though I suspect that we'd need to do some work there.  That is, both to get 1MB keys into DNS reliably (ECH configs are currently 71 bytes typically) as well as to improve caching and reuse so that the 1200:1 ratio could be realized.  Right now, I suspect that the ratio for ECH is closer to OHTTP can easily reach that sort of ratio, which makes McEliece a viable option there.