A Hybrid Post-Quantum KEM for the Messaging Layer Security (MLS) Protocol

1.1. Relationship to the MLS Combiner Draft

This document is not an update to [I-D.ietf-mls-combiner]. That document specifies a different mechanism: two complete MLS sessions are run in parallel over the same membership, and hybrid security is obtained by exporting a secret from the post-quantum session and importing it into the traditional session as a Pre-Shared Key, carried by an ordinary PreSharedKey proposal. It contains no per-commit key mixing step, no classical and post-quantum shared secret pair, and no combiner context string. The requirements in this document therefore have no counterpart in its text.¶

The two approaches are alternatives rather than revisions of one another. The parallel session approach requires no new cryptographic primitive and runs on unmodified MLS implementations, at the cost of duplicated group state, KeyPackages and commit traffic. The approach specified here requires a new ciphersuite and changes to the tree KEM, and keeps a single group state and a single commit stream.¶

3.1. Multi-Input Extension

For n > 2 inputs, callers MUST sort the algorithm identifiers lexicographically, append lv(ALG_i) to ctx_enc in that order, and append lv(K_i) || lv(ct_i) || lv(pk_i) to IKM in the same order.¶

The number of fields is determined by the algorithm list carried in ctx_enc. Together with universal length prefixing, this keeps the encoding injective for every n.¶

7.1. State

Each member MUST maintain the following additional state.¶

S_t:

The post-quantum ratchet secret for the current epoch t, of length L.¶

pq_rotation_counter:

The number of commits since the most recent rotation.¶

pq_rotation_ctx:

An injective encoding binding the epoch and confirmed transcript hash of the most recent rotation.¶

The counter and the rotation context MUST be carried in a GroupContext extension, so that every member derives them identically.¶

7.2. Rotation Policy

A commit MUST be a rotation if pq_rotation_counter has reached k, or if the commit contains an Add, Remove or ReInit proposal, or if the commit is an external commit. The counter MUST be reset to zero on every rotation, from either cause, so that the window is at most k commits.¶

The rotation interval k MUST be fixed by the ciphersuite. It MUST NOT be negotiable, carried in any message field, or otherwise influenced by group members. A negotiable window would be an attacker-influenceable parameter whose only useful direction of attack is to widen it, lengthening exposure and delaying recovery.¶

Ciphersuites defined by this document use k = 32. The reasoning behind that value is given in Section 7.7. Ciphersuites defined elsewhere MUST state their own value of k, and SHOULD justify it against the same considerations.¶

The requirement to rotate on membership change is load bearing. A removed member holds S_t at the moment of its removal, and the ratchet step of Section 7.4 is a public function of S_t and public context. Absent a rotation, a removed member could compute all successor values indefinitely and would retain the post-quantum half of the group's protection after removal.¶

7.3. Enforcement

Recipients MUST independently compute whether the current commit is required to be a rotation, and MUST reject any commit that fails to carry a post-quantum direct path update when one is required, or whose pq_rotation_counter does not match their own computation.¶

Implementations MUST NOT accept a commit on the grounds that the committer asserted no rotation was due. Without this check, a malicious committer could decline to rotate indefinitely, reducing the construction to classical MLS with a stale secret mixed in.¶

7.4. Ratchet

On a rotation at epoch r with post-quantum root secret P_r, the ratchet is initialised as follows.¶

S_r = HKDF-Expand(
          HKDF-Extract(mix_ctx_r, lv(P_r)),
          "pq-ratchet-init", L)

On every other epoch, the ratchet is advanced as follows.¶

S_t+1 = HKDF-Expand(
            HKDF-Extract(mix_ctx_t+1, lv(S_t)),
            "pq-ratchet-step", L)

S_t MUST be zeroized immediately after S_t+1 is derived.¶

Implementations MUST NOT retain P_r beyond the derivation of S_r, and MUST NOT carry P_r forward in place of the ratcheted value. Carrying a constant value forfeits forward secrecy across the entire rotation window on a single compromise.¶

The ratchet step and the mixing step of Section 7.5 share mix_ctx_t, which is available only once the confirmed transcript hash for epoch t has been computed. Implementations MUST sequence the epoch as follows: compute confirmed_transcript_hash_t, derive S_t from S_t-1, zeroize S_t-1, then derive hybrid_commit_secret_t. The two formulae are not circular, but the ordering is normative rather than an implementation detail.¶

7.5. Mixing

The epoch's classical commit_secret, as defined in [RFC9420], and the ratchet secret MUST be combined as follows.¶

mix_ctx_t = lv("MLS-Async-Hybrid-Mixer")
            || version
            || lv(group_id)
            || epoch_t
            || lv(confirmed_transcript_hash_t)
            || lv(ALG_C)
            || lv(ALG_P)
            || lv(pq_rotation_ctx)

hybrid_commit_secret_t =
    HKDF-Extract(salt = mix_ctx_t,
                 IKM  = lv(commit_secret_t) || lv(S_t))

hybrid_commit_secret_t MUST be used wherever MLS uses commit_secret.¶

pq_rotation_ctx MUST be included. It binds the ratchet state to the rotation that produced it, and prevents substitution of a state descended from a different rotation. On a non-rotation commit there is no post-quantum ciphertext to bind, so this field takes the place of the per-node ciphertext binding required by Section 3.¶

7.6. Failure Handling in Asynchronous Mode

On rotation commits, Section 6 applies unchanged.¶

On non-rotation commits there is no post-quantum decapsulation and therefore no decapsulation failure. However, if a member's S_t is absent, corrupt, or inconsistent with pq_rotation_ctx, the member MUST abort processing and re-synchronise. It MUST NOT derive hybrid_commit_secret from commit_secret alone, which would be a silent downgrade to classical-only operation.¶

7.7. Rationale for the Rotation Interval

This subsection is non-normative. It records why k = 32 was selected, so that the choice can be revisited on the same basis if ML-KEM parameters, MLS framing, or deployment evidence change.¶

k sets the average post-quantum cost of a commit and not the peak. A rotation commit carries the full post-quantum direct path whatever k is. Deployments whose binding constraint is maximum message size or fragmentation gain nothing from raising k, and should use synchronous operation instead.¶

The trigger counts commits rather than elapsed time because Section 7.3 requires every recipient to compute independently whether a rotation is due. That is possible only when the trigger is a deterministic function of shared group state. MLS carries no clock in the GroupContext, so a time bound would leave members with skewed clocks rejecting each other's honest commits, or would reduce to the committer asserting that the deadline had not passed, which is what Section 7.3 exists to prevent.¶

Post-quantum cost falls as 1/k and saturates quickly, while the exposure window grows linearly in k and does not saturate. Beyond a certain point each doubling of k buys a fraction of a percent of bandwidth in exchange for twice the worst-case recovery delay.¶

The value was therefore chosen as the smallest k at which post-quantum material ceases to dominate the commit. For a group of 1000 members (h = 10) using ML-KEM-768, a rotation commit carries 2272 bytes per node, being one 1088-byte ciphertext and one 1184-byte public key, or about 22.2 KiB in total. Against a classical direct path of roughly 1.3 KiB for the same tree, k = 32 reduces the overhead of a commit from about 18 times the classical baseline to about 1.5 times, capturing roughly 97 percent of the available reduction. k = 64 recovers a further 1.5 percentage points for twice the window, and k = 16 leaves the post-quantum contribution roughly equal to the entire classical commit.¶

k bounds commits and not elapsed time, and the two are related by a commit rate that varies by orders of magnitude between deployments. No fixed constant can bound both, which argues for choosing conservatively. Two effects limit the consequences: membership changes force a rotation, so k binds only in membership-stable groups, and the window is exploitable only by an adversary that has both compromised ratchet state and broken the classical KEM.¶

Making k a function of group size was considered. It would satisfy Section 7.3, since the tree is shared state, and would let one ciphersuite serve a wide range of group sizes. It is not adopted here because it would weaken the property that the worst-case window is known from the ciphersuite alone, group size being something participants can influence, and because the case for it rests on commit-rate measurements that are not yet available. A clamped form, with a coefficient, a floor and a ceiling all registered alongside the ciphersuite, would bound the worst case and remains the natural candidate if evidence later shows that a single constant serves the extremes of the size range badly.¶

8.1. PRK and Intermediate State Handling

PRK is a per-invocation secret. Implementations MUST NOT cache PRK across invocations, MUST NOT write PRK to persistent storage, and MUST NOT reuse PRK across distinct combinations of CTX, algorithms and combiner_version, even when one or more K_i are unchanged between invocations.¶

This requirement is generic KDF hygiene in synchronous operation, but it is load bearing in asynchronous mode. Because one input is unchanged between rotations, a PRK object held across epochs is an obvious implementation shortcut. mix_ctx_t includes the epoch and the confirmed transcript hash, so the extract input does differ at every epoch and a correct implementation has no reusable value; the risk is that a long-lived PRK object in an HKDF or HPKE wrapper keeps material alive that the ratchet of Section 7.4 is required to have destroyed.¶

PRK, IKM, every K_i, and any platform scratch buffers used by the KDF MUST be zeroized before the combiner returns. KEY itself MUST NOT be reused across commits.¶

8.2. Security Properties of Asynchronous Mode

Let R be the set of rotation epochs, and for an epoch t let r(t) be the greatest element of R that is less than or equal to t. The epoch secret at epoch t is pseudorandom if either of the following holds.¶

1. The classical KEM is secure at epoch t, and the classical state is uncompromised, by the standard MLS argument.¶
2. The post-quantum KEM was secure at epoch r(t), and no member's post-quantum ratchet state was compromised at any epoch in the interval from r(t) to t inclusive.¶

The second condition is weaker than its synchronous counterpart, which reads simply that the post-quantum KEM is secure at epoch t. The one-way ratchet of Section 7.4 sharpens it: a compromise at epoch u exposes only the epochs from u up to the next rotation, and not those preceding u.¶

Forward secrecy therefore holds within the rotation window. Post-quantum post-compromise security does not hold within the window, and is restored only at the next rotation: within k commits, and immediately on any membership change.¶

Because S_t is mixed into the key schedule of every epoch, and not only into rotation epochs, there is no epoch whose secret depends on the classical primitive alone. An adversary that has broken the classical KEM entirely still cannot derive any epoch secret without the post-quantum material.¶

Implementations MUST document the rotation interval k of each ciphersuite they support, so that deployments can evaluate the worst-case post-compromise recovery delay.¶

9.1. MLS Hybrid KEM Combiner Versions

The registration policy for this registry is Specification Required. Each entry contains a version value (an 8-bit unsigned integer), a name, a reference, and a change controller. The initial contents are as follows.¶

9.2. MLS Hybrid KEM Algorithm Identifiers

The registration policy for this registry is Specification Required. Each entry contains an identifier, the name of the KEM, the length in bytes of its shared secret output, whether the KEM is classical or post-quantum, a reference, and a change controller.¶

A registration whose shared secret output is shorter than 256 bits MUST NOT be accepted, as required by Section 5. The initial contents are as follows.¶

9.3. MLS Ciphersuites

This document requests allocation of MLS ciphersuite code points pairing each registered classical KEM with each registered post-quantum KEM. A ciphersuite that supports asynchronous mode (Section 7) MUST register its rotation interval k as part of the ciphersuite definition, because k is not negotiable. The ciphersuites requested by this document register k = 32, for the reasons given in Section 7.7.¶