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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

Actually, in theory, a generic mKEM wouldn’t be that difficult.


  *   Have the signer pick a 32 byte secret X (and the ultimate secret will be the hash(X || full mKEM ciphertext) )
  *   For each recipient, generate a KEM ciphertext and also that shared secret XORed with X; the concatenation of those (along with any needed identifiers to allow parsing and selection of the appropriate ciphertext) is the full mKEM ciphertext.
The way each recipient reconstructs the ultimate shared secret should be obvious (and the additional size of the XOR, which is 32 bytes, is tiny compared to the ML-KEM ciphertext).

And while I don’t have a proof at hand, it is plausible that the ciphertexts and the XORs do not allow someone without any of the private keys to do anything.

From: Blumenthal, Uri - 0553 - MITLL <[e-mail]>
Sent: Wednesday, October 9, 2024 10:56 AM
To: John Mattsson <john.mattsson=[e-mail]>; IRTF CFRG <[e-mail]>
Subject: [CFRG] Re: CFRG (or NIST) should specify multi-KEM (mKEM)

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]<mailto:john.mattsson=[e-mail]>>
Date: Wednesday, October 9, 2024 at 02:46
To: IRTF CFRG <[e-mail]<mailto:[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://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