[CFRG] CFRG (or NIST) should specify multi-KEM (mKEM)

[John Mattsson <[e-mail]>]

Hi,

ECDH-KEM, ML-KEM, and HPKE are all designed for a single recipient. This makes them quite unsuitable for protocols with multiple recipients such as S/MIME, COSE, and JOSE, etc. Today RSA (RSA-OEAP or RSA-KEM) is typically used in protocols with multiple recipients as then can be used to "ecapsulate" the same key to many recipients.

If NIST is not specifying multi-KEMs (mKEMs), I strongly think CFRG should. CFRG should likely also specify a multi-HPKE API to use with mKEMs. An obvious benefit of mKEMs is to avoid having two keywrap layers, but for some algorithms such as ML-KEM the benefits are much larger and the total cipher can be made significantly smaller than 'number of recipients' * 'size of single recipient ciphertext'. Building multi-recipient protocols based on the current single-KEM ML-KEM as specified in FIPS 203 is funndamentally the wrong approach.

mKEMs have been a research topic for 20 years and in parallel with the NIST PQC project there has been a lot of work on mKEM variants of ML-KEM.

https://link.springer.com/chapter/10.1007/978-3-540-30598-9_15

https://cryptojedi.org/papers/mkem-20220812.pdf

https://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-standardization-conference/documents/papers/how-multi-recipient-kems.pdf

https://github.com/cryptojedi/kyber-mkem

Cheers,
John