The ML-KEM Braid is a Sparse Continuous Key Agreement (SCKA) protocol that uses NIST standardized ML-KEM [1] to allow two parties to produce a sequence of post-quantum secure shared secrets. These shared secrets have Forward Secrecy (FS) and Post-Compromise Security (PCS) properties that can carry over to higher level protocols such as a Double Ratchet protocol for secure messaging [2].
1.1 Sparse Continuous Key Agreement
The ping-pong style key exchange at the heart of the classical Double Ratchet protocol is called a Continuous Key Agreement (CKA) protocol. It has the desirable feature that it emits new shared secrets at every round trip, and these secrets can be passed to a higher-level protocol - like the Double Ratchet - to provide Post-Compromise Security.
The messages that must be passed for quantum-secure key agreement are much larger, though, so in the presence of bandwidth constraints a protocol may send these messages in pieces and will not be able to emit new shared secrets in each round trip. To capture this we follow [3] and use the notion of Sparse Continuous Key Agreement (SCKA).
An SCKA protocol outputs an ordered sequence of shared secrets, and the position of a shared secret in this sequence is an unsigned integer called the epoch identifier, or simply the epoch. The notion of epoch is implicit in the Diffie-Hellman ratchet of the classic Double Ratchet protocol [2], but in that context the public ratchet key is sufficient to serve as the epoch identifier. In contrast, we need stronger property, such as the ability to strictly order the epochs without gaps, in order to ensure that we use the output keys correctly.
In an SCKA protocol, each party maintains state and exposes two functions:
Send(state) -> (msg, sending_epoch, output_key): Updates the state and returns msg, a message to be processed by the other party, sending_epoch, the identifier of the latest epoch guaranteed to be known by the other party on receipt of msg, and output_key, a nullable pair containing an epoch identifier and a shared secret for that epoch.
Receive(state, msg) -> (receiving_epoch, output_key): Updates the state and returns receiving_epoch, the epoch identifier that was output by the other party as sending_epoch when they called send() to generate msg, and output_key, a nullable pair containing an epoch identifier and a shared secret for that epoch.
Precise correctness and security definitions are given in [3]. Informally, for correctness, the two parties in the protocol must agree on the sequence of keys emitted and the values of sending_epoch and receiving_epoch must indicate the most recent epochs that can be used correctly.
- Session key consistency: If Alice and Bob output keys (ep, k) and (ep', k') respectively where ep = ep', then k = k'.
- Per-participant epoch uniqueness: Each party outputs at most one key per epoch.
- Sender epoch knowledge: When Send() returns sending_epoch, the sender possesses, or has possessed, the key for that epoch and all earlier epochs.
- Receiver epoch knowledge: When Receive() returns receiving_epoch, the receiver possesses, or has possessed, the key for that epoch and all earlier epochs.
- Epoch agreement: sending_epoch from Send() equals receiving_epoch from the corresponding Receive(). Specifically, if Alice (respectively, Bob) calls Send() which returns msg and sending_epoch, then when Bob (respectively, Alice) calls Receive(msg), it must return receiving_epoch = sending_epoch.
1.2 Incremental KEMs
Some lattice-based Key Encapsulation Mechanisms (KEMs) based on the Learning With Errors assumption take the form of a "noisy key exchange" followed by a small reconciliation message that allows the parties to arrive at an exact shared secret. Because of this, the ciphertexts for these KEMs consist of two parts: ct1 is a possibly compressed public key and ct2 is a reconciliation message. The important observation is that ct1 can be computed without complete knowledge of any encapsulation key.
To allow KEM users to take advantage of this fact, these KEMs can expose the following incremental interface:
KeyGen(randomness) -> (dk, ek_header, ek_vector): Takes an array of random bits and returns a decapsulation key, dk, an ek_header with all information needed for a recipient to calculate ct1, and the "vector" part of the encapsulation key, ek_vector. We note that for some KEMs it is possible that the header could be empty.
Encaps1(ek_header, randomness) -> (encaps_secret, ct1, shared_secret): Takes an encapsulation key header and an array of random bits as input and samples the first part of a new ciphertext. It returns encaps_secret, an encapsulation secret that holds the information needed to complete the encapsulation, ct1, the first component of a ciphertext, and shared_secret, the shared secret encapsulated by the ciphertext.
Encaps2(encaps_secret, ek_header, ek_vector) -> ct2: Takes an encapsulation secret, encapsulation key header, and encapsulation key vector and completes the encapsulation process, returning a reconciliation message, ct2.
Decaps(dk, ct1, ct2) -> shared_secret: Takes a decapsulation key and a complete ciphertext and returns the encapsulated shared secret.
1.2.1 ML-KEM as an Incremental KEM
ML-KEM [1] encapsulation keys consist of a 32-byte seed followed by a larger noisy vector. This seed is required to compute the "compressed public key" part of a ciphertext, ct1. Due to the Fujisaki-Okamoto transform [4] variant used by ML-KEM, we also need to know the SHA3-256 hash of the full encapsulation key to compute ct1. Thus an encapsulation key header for ML-KEM has the following fields:
- ek_seed: A 32-byte seed.
- hek: The SHA3-256 hash of ek_seed || ek_vector.
As discussed in Section 3.2, ML-KEM use of the encapsulation key hash gives it key binding properties that go beyond standard IND-CCA security and this should be considered when evaluating the use of any alternate KEM.
1.3 Chunking with Erasure Codes
An SCKA protocol sends large messages in pieces and must do this in a way that is robust, even in an adversarial network environment. To accomplish this a protocol can use erasure codes or fountain codes. Informally this can be thought of as breaking a message into a stream of chunks, and in this document any mention of a "chunk" of a message refers to a codeword of an erasure code.