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

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

Specifying an mKEM seems a good idea to me. I suspect that it would (necessarily) have different (lower) security guarantees, but a construct tike this is needed. 

-- 
V/R, 
Uri 

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies. 
The other is to make it so complex there are no obvious deficiencies. 
C. A. R. Hoare 

I was a shepherd to fools 
Causelessly bold or afraid. 
They would not abide by my rules. 
Yet they escaped. For I stayed. 
R. Kipling “Epitaphs of the War. Convoy Escort” 



From: John Mattsson <john.mattsson=[e-mail]>
Date: Wednesday, October 9, 2024 at 02:46
To: IRTF CFRG <[e-mail]>
Subject: [EXT] [CFRG] CFRG (or NIST) should specify multi-KEM (mKEM) 

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 

ZjQcmQRYFpfptBannerStart 

This Message Is From an External Sender 

This message came from outside the Laboratory. 





ZjQcmQRYFpfptBannerEnd 

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://link.springer.com/chapter/10.1007/978-3-540-30598-9_15> 

https://cryptojedi.org/papers/mkem-20220812.pdf <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://csrc.nist.gov/csrc/media/Events/2024/fifth-pqc-standardization-conference/documents/papers/how-multi-recipient-kems.pdf> 

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

Cheers, 
John