Hybrid PQ/T Key Encapsulation Mechanisms

5.1.1. Using a Nominal Group

Hybrid KEM frameworks that use a nominal group for the traditional component invoke the DeriveKeyPair, Encaps, and Decaps functions of PQ KEMs, alongside analogous functions of the nominal group. The "encapsulation key" is the receiver's public key group element; the "ciphertext" is an ephemeral group element; and the shared secret is the secret value resulting from an ephemeral-static Diffie-Hellman exchange.¶

def expandDecapsKeyG(seed):
    seed_full = PRG(seed)
    (seed_PQ, seed_T) = split(KEM_PQ.Nseed, Group_T.Nseed, seed_full)

    (ek_PQ, dk_PQ) = KEM_PQ.DeriveKeyPair(seed_PQ)
    dk_T = Group_T.RandomScalar(seed_T)
    ek_T = Group_T.Exp(Group_T.g, dk_T)

    return (ek_PQ, ek_T, dk_PQ, dk_T)

def prepareEncapsG(ek_PQ, ek_T):
    (ss_PQ, ct_PQ) = KEM_PQ.Encaps(ek_PQ)
    sk_E = Group_T.RandomScalar(random(Group_T.Nseed))
    ct_T = Group_T.Exp(Group_T.g, sk_E)
    ss_T = Group_T.ElementToSharedSecret(Group_T.Exp(ek_T, sk_E))
    return (ss_PQ, ss_T, ct_PQ, ct_T)

def prepareDecapsG(ct_PQ, ct_T, dk_PQ, dk_T):
    ss_PQ = KEM_PQ.Decap(dk_PQ, ct_PQ)
    ss_T = Group_T.ElementToSharedSecret(Group_T.Exp(ct_T, dk_T))
    return (ss_PQ, ss_T)

5.1.2. Using a Traditional KEM

Hybrid KEM frameworks that use a KEM for the traditional component invoke the DeriveKeyPair, Encaps, and Decaps functions of the traditional and PQ KEMs in parallel.¶

def expandDecapsKeyK(seed):
    seed_full = PRG(seed)
    (seed_PQ, seed_T) = split(KEM_PQ.Nseed, KEM_T.Nseed, seed_full)
    (ek_PQ, dk_PQ) = KEM_PQ.DeriveKeyPair(seed_PQ)
    (ek_T, dk_T) = KEM_T.DeriveKeyPair(seed_T)
    return (ek_PQ, ek_T, dk_PQ, dk_T)

def prepareEncapsK(ek_PQ, ek_T):
    (ss_PQ, ct_PQ) = KEM_PQ.Encap(ek_PQ)
    (ss_T, ct_T) = KEM_T.Encap(ek_T)
    return (ss_PQ, ss_T, ct_PQ, ct_T)

def prepareDecapsK(ct_PQ, ct_T, dk_PQ, dk_T):
    ss_PQ = KEM_PQ.Decap(dk_PQ, ct_PQ)
    ss_T = KEM_T.Decap(dk_T, ct_T)
    return (ss_PQ, ss_T)

5.1.3. Combiners

A combiner function uses the KDF used in the hybrid KEM to combine the shared secrets output by the component algorithms with contextual information.¶

The two combiner functions defined in this document are as follows:¶

def UniversalCombiner(ss_PQ, ss_T, ct_PQ, ct_T, ek_PQ, ek_T, label):
    KDF(concat(ss_PQ, ss_T, ct_PQ, ct_T, ek_PQ, ek_T, label))

def C2PRICombiner(ss_PQ, ss_T, ct_T, ek_T, label):
    KDF(concat(ss_PQ, ss_T, ct_T, ek_T, label))

Note that while the names of the inputs are suggestive of the shared secret, ciphertext, and encapsulation key outputs of a KEM, the inputs to this function in the hybrid KEM framework are not necessarily the output of a secure KEM. In particular, when the framework is instantiated with a nominal group, the "ciphertext" component is an ephemeral group element, and the "encapsulation key" is the group element that functions as the recipient's public key.¶

The choice of combiner brings with it certain assumptions under which the resulting hybrid KEM is secure.¶

The UniversalCombiner combiner explicitly computes over shared secrets, ciphertexts, and encapsulation keys from both components. This allows the resulting hybrid KEM to be secure as long as either component is secure, with no further assumptions on the components.¶

The C2PRICombiner combiner does not compute over the ciphertext or encapsulation key from the PQ component. The resulting hybrid KEM will be secure if the PQ component is IND-CCA secure, or, the traditional component is secure and the PQ component also satisfies the C2PRI property.¶

6.1.1. Indistinguishability under Chosen Ciphertext Attack (IND-CCA)

The first goal we have for our hybrid KEM constructions is indistinguishability under adaptive chosen ciphertext attack, or IND-CCA [BHK09]. This is most common security goal for KEMs and public-key encryption.¶

For KEMs, IND-CCA requires that no efficient adversary, given a ciphertext obtained by running Encaps() with an honestly-generated public key, can distinguish whether it is given the "real" secret output from Encaps(), or a random string unrelated to the Encaps() call that created that ciphertext. (Readers should note that this definition is slightly different than the corresponding definitions for public-key encryption [BHK09].)¶

Whether a given KEM provides IND-CCA depends on whether the attacker is assumed to have access to quantum computing capabilities or not (assuming the scheme is without bugs and the implementation is correct). Post-quantum KEMs are intended to provide IND-CCA security against such an attacker. Traditional KEMs are not.¶

IND-CCA is the standard security notion for KEMs; most PQ KEMs were explicitly designed to achieve this type of security against both a quantum attacker and a traditional one.¶

For traditional algorithms, things are less clear. The DHKEM construction in [RFC9180] is an IND-CCA KEM based on Diffie-Hellman [ABH_21], but "raw" ephemeral-static Diffie-Hellman, interpreting the ephemeral public key as the ciphertext, is not IND-CCA secure. RSA-KEM is IND-CCA secure [ISO18033-2], and RSA-OAEP public-key encryption can be used to construct an IND-CCA KEM, but "classical" RSA encryption (RSAES-PKCS1-v1_5 as defined in [RFC8017]) is not even IND-CCA secure as a public-key encryption algorithm.¶

6.1.2. Ciphertext Second-Preimage Resistence (C2PRI)

Ciphertext Second-Preimage Resistence (C2PRI) is the property that given an honestly generated ciphertext, it is difficult for an attacker to generate a different ciphertext that decapsulates to the same shared secret. In other words, if an honest party computes (ss, ct) = Encaps(ek), then it is infeasible for an attacker to find another ciphertext ct' such that Decaps(dk, ct) == ss (where dk is the decapsulation key corresponding to the encapsulation key ek).¶

A related notion in the literature is chosen-ciphertext resistance (CCR) [CDM23]. C2PRI targets preimage-resistance, whereas CCR targets collision-resistance, much like the analogous properties for hash functions. In the language of the binding properties discussed in Section 6.1.4, CCR is equivalent to the property LEAK-BIND-K,PK-CT.¶

C2PRI is a weaker property than CCR / LEAK-BIND-K,PK-CT because it requires the attacker to match a specific, honestly generated ciphertext, as opposed to finding an arbitrary pair.¶

Several PQ KEMs have been shown to have C2PRI. ML-KEM was shown to have this property in [XWING], and [CHH_25] proves C2PRI for several other algorithms, including FrodoKEM, HQC, Classic McEliece, and sntrup.¶

6.1.3. Strong Diffie-Hellman Problem (SDH)

The standard Diffie-Hellman problem is whether an attacker can compute g^xy given access to g^x and g^y and an oracle DH(Y, Z) that answers whether Y^x = Z. (This is the notion specified in [XWING], not the notion of the same name used in the context of bilinear pairings [Cheon06].)¶

When we say that the strong Diffie-Hellman problem is hard in a group, we always mean this in the context of classical attackers, without access to quantum computers. An attacker with access to a quantum computer that can execute Shor's algorithm for a group can efficiently solve the discrete log problem in that group, which implies the ability to solve the strong Diffie-Hellman problem.¶

As shown in [ABH_21], this problem is hard in prime-order groups such as the NIST elliptic curve groups P-256, P-384, and P-521, as well as in the Montgomery curves Curve25519 and Curve448.¶

6.1.4. Binding Properties

It is often useful for a KEM to have certain "binding" properties, by which certain parameters determine certain others. Recent work [CDM23] gave a useful framework of definitions for these binding properties. Binding for KEMs is related to other properties for KEMs and public-key encryption, such as robustness [GMP22] [ABN10], and collision-freeness [MOHASSEL10].¶

The framework given by [CDM23] refers to these properties with labels of the form X-BIND-P-Q. The first element X is the model for how the attacker can access the decapsulation key: HON for the case where the attacker never accesses the decapsulation key, LEAK for the case where the attacker has access to the honestly-generated decapsulation key, or MAL for the case where the attacker can choose or manipulate the keys used by the victim. P,Q means that given the value P, it is hard to produce another Q that causes Decaps to succeed. For example, LEAK-BIND-K-PK means that for a given shared secret (K), there is a unique encapsulation key (PK) that could have produced it, even if all of the secrets involved are given to the adversary after the encapsulation operation is completed (LEAK).¶

There is quite a bit of diversity in the binding properties provided by KEMs. Table 5 of [CDM23] shows the binding properties of a few KEMs. For example: DHKEM provides MAL-level binding for several properties. ML-KEM provides only LEAK-level binding. Classic McEliece provides MAL-BIND-K-CT, but no assurance at all of X-BIND-K-PK.¶

6.1.5. Indifferentiability from a Random Oracle

The KDF used with a hybrid KEM MUST be indifferentiable from a random oracle (RO) [MRH03], even to a quantum attacker [BDFL_10] [ZHANDRY19]. This is a conservative choice given a review of the existing security analyses for our hybrid KEM constructions: most IND-CCA analyses for the four frameworks require only that the KDF is some kind of pseudorandom function, but the SDH-based IND-CCA analysis of CG in [XWING], and the corresponding analysis for UG (forthcoming) relies on the KDF being a RO. Proofs of our target binding properties for our hybrid KEMs require the KDF is a collision-resistant function.¶

If the KDF is a RO, the key derivation step in the hybrid KEMs can be viewed as applying a (RO-based) pseudorandom function - keyed with the shared secrets output by the constituent KEMs - to the other inputs. Thus, analyses which require the KDF to be a PRF, such as the one given in [GHP18] for UK, or the standard-model analysis of CG in [XWING], apply.¶

Sponge-based constructions such as SHA-3 have been shown to be indifferentiable against classical [BDP_08] as well as quantum adversaries [ACM_25].¶

HKDF has been shown to be indifferentiable from a random oracle under specific constraints [LBB20]:¶

• that HMAC is indifferentiable from a random oracle, which for HMAC-SHA-256 has been shown in [DRS_13], assuming the compression function underlying SHA-256 is a random oracle, which it is indifferentiably when used prefix-free.¶

• the values of HKDF's IKM input do not collide with values of info || 0x01. This MUST be enforced by the concrete instantiations that use HKDF as its KDF.¶

The choice of the KDF security level SHOULD be made based on the security level provided by the constituent KEMs. The KDF SHOULD at least have the security level of the strongest constituent KEM.¶

6.1.6. Security Requirements for PRGs

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]. A secure PRG is an algorithm PRG : {0, 1}ⁿ → {0, 1}^m, such that no polynomial-time adversary can distinguish between PRG(r) (for r $← {0, 1}ⁿ) and a random z $← {0, 1}^m [Rosulek]. The uniform string r ∈ {0, 1}ⁿ 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.¶

6.2.1. IND-CCA Security

The idea of a hybrid KEM is that it should maintain its security if only one of the two component KEMs is secure. For a PQ/T hybrid KEM, this means that the hybrid KEM should be secure against a quantum attacker if the T component is broken, and secure against at least a classical attacker if the PQ component is broken.¶

More precisely, the hybrid KEM should meet two different notions of IND-CCA security, under different assumptions about the component algorithms:¶

• IND-CCA against a classical attacker all of the following are true:¶

  • KDF is indifferentiable from a random oracle¶

  • If using Group_T: The strong Diffie-Hellman problem is hard in Group_T¶

  • If using KEM_T: KEM_T is IND-CCA against a classical attacker¶

  • If using C2PRICombiner: KEM_PQ is C2PRI¶

• IND-CCA against a quantum attacker if all of the following are true:¶

  • KDF is indifferentiable from a random oracle¶

  • KEM_PQ is IND-CCA against a quantum attacker¶

Some IND-CCA analyses do not strictly require the KDF to be indifferentiable from a random oracle; they instead only require a kind of PRF assumption on the KDF. For simplicity we ignore this here; the security analyses described below for our constructions will elaborate on this point when appropriate.¶

6.2.2. Binding Properties

The most salient binding properties for a hybrid KEM to be used in Internet protocols are LEAK-BIND-K-PK and LEAK-BIND-K-CT.¶

The LEAK attack model is most appropriate for Internet protocols. There have been attacks in the LEAK model [BJKS24] [FG24], so a hybrid KEM needs to be resilient at least to LEAK attacks (i.e., HON is too weak). Internet applications generally assume that private keys are honestly generated, so MAL is too strong an attack model to address.¶

The LEAK-BIND-K-PK and LEAK-BIND-K-CT properties are naturally aligned with the needs of protocol design. Protocols based on traditional algorithms frequently need to incorporate transcript hashing in order to protect against key confusion attacks [FG24] or KEM re-encapsulation attacks [BJKS24]. The LEAK-BIND-K-PK and LEAK-BIND-K-CT properties prevent these attacks at the level of the hybrid KEM. Protocol designers may still need or want to include the ciphertext or encapsulation key into their protocol or key schedule for other reasons, but that can be independent of the specific properties of the KEM and its resulting shared secret.¶

Implementors should not interpret the paragraph above as absolving them of their responsibility to carefully think through whether MAL-BIND attacks apply in their settings.¶

6.4.1. IND-CCA analyses

The UG construction has two complementary IND-CCA analyses: one for when the SDH problem holds but the PQ KEM is broken, and one for the reverse. Both are technically novel but are substantially similar to the existing peer-reviewed analyses of the CG [XWING] and UK [GHP18] constructions. A forthcoming document by the editorial team will describe the analysis of UG in detail.¶

The first IND-CCA analysis, based on SDH, is very similar to the corresponding analysis of CG given in [XWING]: it gives a straightforward reduction to the SDH hardness in the underlying group. Notably, since the PQ KEM key and ciphertext are hashed, the C2PRI security of the PQ KEM does not appear in the bound.¶

The second IND-CCA analysis is a straightforward reduction to the IND-CCA security of the PQ KEM, and the PRF security of the RO when keyed with the PQ KEM's shared secret.¶

This document's UK construction does not have an IND-CCA analysis; the [GHP18] paper on which the construction is based gives a slightly different version, namely they do not include the public encapsulation keys in the KDF. However, we argue that the proof goes through with trivial modifications if the public encapsulation keys are included in the KDF. The relevant step is claim 3 of Theorem 1, which reduces to the split-key pseudorandomness of the KDF. ([GHP18] call the KDF a "core" function, and denote it as W.) We observe that adding the public encapsulation keys to the inputs only changes the concrete contents of the reduction's queries to its oracle. Since the reduction chooses the public encapsulation keys itself, they can be added to the oracle inputs, and the remainder of the proof goes through unmodified.¶

We reiterate that modulo some low-level technical details, our requirement that the KDF is indifferentiable from an RO implies that, in the ROM, the KDF used in [GHP18] meets the split-key pseudorandomness property used in [GHP18]'s analysis: this is shown in [GHP18], Lemma 6, where a pseudorandom skPRF is constructed from any almost-uniform keymixing function in the random oracle model by H(g(k1,...,kn), x) , where H is modeled as a random oracle and g is ϵ-almost uniform. Example 3 from [GHP18] qualifies g(k_1,...,k_n) = k_1 || ... || k_n as ϵ-almost uniform with ϵ = 1/len(k_1 || ... || k_n).¶

Like UG, the CG construction has two complementary IND-CCA analyses. Both were given in [XWING]. We summarize them but elide some details.¶

One analysis (Theorem 1) [XWING] shows that if the KDF is modelled as a RO, IND-CCA holds if the PQ KEM is broken, as long as the SDH problem holds in the nominal group and the PQ KEM satisfies C2PRI. The other (Theorem 2) [XWING] shows that if the PQ-KEM is IND-CCA and the KDF is a PRF keyed on the PQ-KEM's shared secret, IND-CCA holds.¶

As long as the aforementioned security requirements of the component parts are met, these analyses imply that this document's CG construction satisfies IND-CCA security.¶

The CK construction's IND-CCA analysis is based on forthcoming work by the editorial team.¶

The CK construction has two complementary IND-CCA analyses: one for when the IND-CCA security of the traditional PKE-based KEM holds but the PQ KEM is broken, except for the PQ KEM's C2PRI security, and one for where the IND-CCA security of the PQ KEM holds. Both are technically novel but are substantially similar to the existing peer-reviewed analyses of the CG [XWING] and UK [GHP18] constructions. A forthcoming document by the editorial team will describe the analysis of CK in detail.¶

Therefore all four hybrid KEMs in this document are IND-CCA when instantiated with cryptographic components that meet the security requirements described above. Any changes to the algorithms, including key generation/derivation, are not guaranteed to produce secure results.¶

6.4.2. Binding analyses

There are four hybrid KEM frameworks, and two target binding properties, so we need eight total analyses. None of these exact results were known; thus the following are new results by the editorial team. We include informal justifications here and defer rigorous proofs to a forthcoming paper.¶

We note that these sketches implicitly ignore the fact that in our hybrid KEMs, both key pairs are derived from a common random seed; we instead implicitly think of them as two runs of DeriveKeyPair with independent random seeds. We justify this simplification by noting that in the LEAK model - in which the adversary is given the key pairs resulting from an honest run of KeyGen - the pseudorandomness of the seed expansion implies the adversary's input distributions in the two cases are computationally indistinguishable. The derivation of component scheme key pairs from the common random seed provides further protection against manipulation or corruption of keys such that it can contribute to stronger binding properties against a MAL adversary, as well as operational benefits in practice, but we do not prove that here.¶

6.5.1. Domain Separation

ASCII-encoded bytes provide oracle cloning [BDG20] in the security game via domain separation. The IND-CCA security of hybrid KEMs often relies on the KDF function KDF to behave as an independent random oracle, which the inclusion of the label achieves via domain separation [GHP18].¶

By design, the calls to KDF in these frameworks and usage anywhere else in higher level protocol use separate input domains unless intentionally duplicating the 'label' per concrete instance with fixed parameters. This justifies modeling them as independent functions even if instantiated by the same KDF. This domain separation is achieved by using prefix-free sets of label values. Recall that a set is prefix-free if no element is a prefix of another within the set.¶

Length differentiation is sometimes used to achieve domain separation but as a technique it is brittle and prone to misuse [BDG20] in practice so we favor the use of an explicit post-fix label.¶

6.5.2. Fixed-length

Variable-length secrets are generally dangerous. In particular, using key material of variable length and processing it using hash functions may result in a timing side channel. In broad terms, when the secret is longer, the hash function may need to process more blocks internally. In some unfortunate circumstances, this has led to timing attacks, e.g. the Lucky Thirteen [LUCKY13] and Raccoon [RACCOON] attacks.¶

Furthermore, [AVIRAM] identified a risk of using variable-length secrets when the hash function used in the key derivation function is no longer collision-resistant.¶

If concatenation were to be used with values that are not fixed-length, a length prefix or other unambiguous encoding would need to be used to ensure that the composition of the two values is injective and requires a mechanism different from that specified in this document.¶

Therefore, this specification MUST only be used with algorithms which have fixed-length shared secrets.¶