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

[Deirdre Connolly <[e-mail]>]

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

Not exactly, see
https://www.ietf.org/archive/id/draft-irtf-cfrg-hybrid-kems-12.html#name-security-requirements-for-p
:

"The functions used to expand a key seed to multiple key seeds is closer to
a pseudorandom generator (PRG) in its security requirements [AOB_24
<https://www.ietf.org/archive/id/draft-irtf-cfrg-hybrid-kems-12.html#AOB_24>].
A secure PRG is an algorithm PRG : {0, 1}n → {0, 1}m, such that no
polynomial-time adversary can distinguish between PRG(r) (for r $← {0, 1}n)
and a random z $← {0, 1}m [Rosulek
<https://www.ietf.org/archive/id/draft-irtf-cfrg-hybrid-kems-12.html#Rosulek>].
The uniform string r ∈ {0, 1}n is called the seed of the PRG.

A PRG is not to be confused with a random (or
pseudorandom) number generator (RNG): a PRG requires the seed randomness to
be chosen uniformly and extend it; an RNG takes sources of noisy data and
transforms them into uniform outputs.

PRGs are related to extendable output functions (XOFs) which can be built
from random oracles. Examples include SHAKE256."

Strictly speaking we don't need a PRF for this use case (seed expansion),
only a PRG, so we don't require it, but in the concrete instances, we do
use functions that are also secure PRFs


On Sat, Jul 11, 2026, 6:42 AM Neil Madden <[e-mail]> wrote:

> 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
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>