[CFRG] Re: RG Last Call on draft-irtf-cfrg-hybrid-kems-12 and draft-irtf-cfrg-concrete-hybrid-kems-04

[Neil Madden <[e-mail]>]

On 8 Jul 2026, at 11:24, Nick Sullivan <[e-mail]> wrote:
> 
> Dear CFRG,
> 
> This message starts a two-week RG Last Call on two related documents. The last
> call ends on Wednesday July 22, 2026:
> 
>   Hybrid PQ/T Key Encapsulation Mechanisms (generic constructions)
>   draft-irtf-cfrg-hybrid-kems-12
>   https://www.ietf.org/archive/id/draft-irtf-cfrg-hybrid-kems-12.html

I've only had a chance to read through this document so far. I think it needs some work still. I haven't followed the development of these documents in much depth, so apologies if anything I raise here has been mentioned before. But perhaps coming at it with fresh eyes may be useful.

The introduction describes KEMs as "standardized", but doesn't link to any standard that defines the KEM API. NIST SP 800-227 is probably the relevant standard to cite. It uses different syntax compared to the draft, however, having explicit parameters passed to each method (which seems to invite the bug of passing inconsistent parameters to KeyGen vs Encaps vs Decaps, but here we are...). I think the equivalent to DeriveKeyPair(seed) would be:

  DeriveKeyPair(seed) = KEM.KeyGen(params; seed)

for some fixed "params". I think the syntax in the draft is clearer, but I think citing SP 800-227 and either using that syntax or showing how it maps would be a good idea.

My immediate thought on seeing the definition with both DeriveKeyPair and GenerateKeyPair was that the latter can be defined in terms of the former with a random seed, so why have both? This is partly addressed later, but it still doesn't seem clear to me. I can see that e.g. a HSM manufacturer may not publicly expose something like DeriveKeyPair in their implementation of ML-KEM, but is it a good idea to implement one of these hybrids outside of the HSM, making use of such an implementation? Or would it be better for the HSM manufacturer to implement the hybrid directly, making use of whatever internals they wish? The draft tries to accommodate both options, which makes it confusing to read IMO. Also, if a private key can either be a seed or a set of component keys depending on the implementation choice, how can a standard using this document specify the format of such a private key? Either define a fully generic black-box construction in terms of established KEM APIs, or else assume that internals are available. Trying to ride both horses is confusing.

Without wishing to open a can of worms, the arguments in the introduction for hybridising PQ and PreQ KEMs would seem to also potentially argue for hybridising two PQ KEMs instead, e.g. ML-KEM and Classic McEliece. (I think Soatok made this point recently). That would also hedge against potential breaks in either, and against implementation errors in either. Or even three-way hybrids of EC+PQ+PQ. If that is an absurd suggestion, the intro should spell out why more clearly - efficiency? Key size? Trust in already deployed code? The wording implies that the constructions in the draft only apply if one of the components is non-PQ, but I think for the KEM-based combiners they should work with any KEM, right? Either tighten up the wording to more clearly state why the draft is only applicable to traditional+PQ combinations, or else widen it to provide generic hybrid constructions regardless of the properties of the components.

Section 4.1:

"In the notation above, Decaps is written as if it always returns an output ss; this is an artifact of the Python-like psuedocode used in this document."

Python has "-> ss | None" ...

4.2:

The term "nominal group" is a new one for me, and Google seems to agree, returning nothing useful for that term. I appreciate there was a good reason for the cited reference to define them when analysing HPKE, but for this document would the much more common (if not entirely accurate) "cyclic group" suffice? Or even just saying ECDH/X25519/X448 directly as that is all anyone is ever really going to use, and the draft already explicit refers to Diffie-Hellman in the description anyway.

4.3:

If the PRG takes a seed and returns a fixed-size output, isn't it in fact a PRF instead?

4.4 - the description of KDFs also sounds more like a PRF.

Section 5:

Unlike some other commentators on this thread, I don't object to defining some generic constructions for C2PRI KEMs if there is a sufficient justification. If I was writing a library to implement this, I would use the type system to (try to) ensure constructions are used appropriately, something like:

  type KEM ...
  type C2PRIKEM extends KEM ...

  def CK(trad: KEM, pq: C2PRIKEM) -> KEM
  def UK(trad: KEM, pq: KEM) -> KEM

Thus enforcing that CK can only be used with a KEM with the additional C2PRI property. Perhaps the draft could capture something like that?

On the other hand, I really dislike having separate constructions for Nominal Groups vs KEMs for the traditional component. Couldn't the draft instead show how to wrap the nominal group into a KEM via (EC)DH-KEM and then define the constructions purely in terms of KEMs?

Section 6.1.1:

The definition of IND-CCA security for KEMs states that the ciphertext should be indistinguishable from a random string, and then states that HPKE's DH-KEM achieves this. But the ciphertext for DH-KEM is a serialized ephemeral public key on the underlying curve, so is trivial to distinguish from a random *string*. As far as I'm aware, DH-KEM doesn't require the use of Elligator or similar. Don't we rather want a left/right definition of indistinguishability, where the attacker has to distinguish between a ciphertext for a challenge key vs a ciphertext for a randomly generated encapsulation key? 

6.1.2:

The notion of C2PRI seems related to key commitment in AEADs. Is that a useful comparison for readers?

6.1.3:

What is the relevance of SDH to the constructions in the document? Is this a requirement on all nominal groups? Again, can it make do with more standard CDH/DDH assumptions?

Best wishes,
Neil