2. The ML-KEM Braid Protocol

2.1 Overview

The ML-KEM Braid protocol takes advantage of the incremental interface ML-KEM described above to parallelize message sending and speed recovery from compromise. Specifically, the incremental interface allows ct1 to be sampled after receiving just a header, after which ct1 and ek_vector - the largest components of the ciphertext and encapsulation key - can be sent in parallel.

The following is a high level description of one epoch of the ML-KEM Braid protocol.

1. A samples a new ML-KEM keypair: (dk, ek_seed, ek_vector) = ML-KEM-KeyGen().
2. A encodes a header message, ek_seed || SHA3-256(ek_seed || ek_vector), and begins sending it to B in chunks.
3. When B receives enough chunks to reconstruct the message, they decode and compute (encaps_secret, ct1, shared_secret) = ML-KEM-Encaps1(ek_seed, SHA3-256(ek_seed || ek_vector)). B stores encaps_secret and shared_secret for later use.
4. B encodes ct1 and begins sending it to A in chunks.
5. When A receives the first chunk of ct1, they stop sending chunks of the header and start sending chunks of ek_vector.
6. Now A and B send their messages in parallel.
7. When A receives all of ct1 they begin acknowledging the receipt in future messages sent to B.
8. Once B receives all of ek_vector and receives an acknowledgment that ct1 was received, they compute ct2 = ML-KEM-Encaps2(encaps_secret, ek_seed, ek_vector).
9. B encodes ct2 and begins sending it to A in chunks.
10. When A receives the first chunk of ct2, they stop sending chunks of ek_vector.
11. When A receives all of ct2, they decapsulate the shared secret: shared_secret = ML-KEM-Decaps(dk, ct1, ct2).
12. Now A and B switch roles. A begins waiting for a header message from B, and indicates it has moved to the next epoch when sending messages to B.
13. Once B receives a message showing that A has advanced to the next epoch, they sample a new keypair and begin again.

While this captures the main flow of the protocol, it does not tell us how A and B know when they can use the keys returned by the protocol. Clearly, when B returns shared_secret above, they cannot use it to encrypt messages to A because A does not know shared_secret yet. This will be addressed by the values sending_epoch and receiving_epoch returned from the functions defined below - a value that tells the caller what latest epoch key known by both parties at the time a message was created.

The protocol below also performs optional authentication, with details presented in Section 2.4 and discussed further in Section 3.3.

2.2 Parameters

• KEM: An IND-CPA secure Key Encapsulation Mechanism that offers an incremental interface. For this document it will be one of ML-KEM-512, ML-KEM-768, or ML-KEM-1024. The KEM exposes the incremental interface described in Section 1.2.

• Constants: Several constants are also associated with the KEM and are needed in the protocol description:

Constant	ML-KEM 512	ML-KEM 768	ML-KEM 1024
HEADER_SIZE	64	64	64
EK_SIZE	768	1152	1536
CT1_SIZE	640	960	1408
CT2_SIZE	128	128	160

• Encode/Decode: An erasure code or fountain code that can encode a long message into a stream of codewords, or chunks, so that when the receiver gets a sufficient number of these chunks, regardless of order or dropped codewords, they will be able to reconstruct the original message. Reed-Solomon based erasure codes over GF(2^16)^(w/2) for a chunk size of w bytes are recommended.

  • Encode(byte_array) -> encoder: Returns a stateful encoding object that produces a stream of codewords, or chunks, that can be decoded to reconstruct byte_array. These codewords are accessed by calling the method encoder.next_chunk().
  • Decoder.new(message_size) -> decoder: Returns a stateful decoding object that will decode a message of length message_size from a set of codewords produced by a single encoder. It exposes the functions:
    • decoder.add_chunk(chunk): Adds a codeword to the decoder's state.
    • decoder.has_message() -> bool: Returns true when the decoder has received enough codewords to reconstruct the message.
    • decoder.message() -> maybe_byte_array: Returns the reconstructed message if possible, otherwise returns Null.

• EPOCH_TYPE: The unsigned integer type used to represent epochs. We recommend using unsigned 64-bit integers.

• ToBytes(epoch): Represent an epoch as a byte string. When EPOCH_TYPE is a 64-bit unsigned integer, use of big-endian encoding is recommended.

• MAC(mac_key, msg): A message authentication code. HMAC-SHA256 is recommended.

• MAC_SIZE: Size of MAC's output, in bytes.

• PROTOCOL_INFO: The concatenation of a protocol identifier, a string representation of KEM, and a string representation of MAC, separated with the delimiter "_", such as "MyProtocol_MLKEM768_SHA-256". The string representations of the ML-KEM Braid parameters are defined by the implementer.

• KDF_AUTH(root_key, update_key, epoch): 64 bytes of output from the HKDF algorithm [5] using hash with inputs:

  • HKDF input key material = update_key
  • HKDF salt = root_key
  • HKDF info = PROTOCOL_INFO || ":Authenticator Update" || ToBytes(epoch)
  • HKDF length = 64

• KDF_OK(shared_secret, epoch): 32 bytes of output from the HKDF algorithm [5] using hash with inputs:

  • HKDF input key material = shared_secret
  • HKDF salt = A zero-filled byte sequence with length equal to the hash output length, in bytes.
  • HKDF info = PROTOCOL_INFO || ":SCKA Key" || ToBytes(epoch)
  • HKDF length = 32

2.3 Messages

Messages consist of the following fields:

• epoch (unsigned integer): Current epoch being negotiated
• type (enum): One of {None, Hdr, Ek, EkCt1Ack, Ct1Ack, Ct1, Ct2} with the following meanings:
  • None: There is no payload
  • Hdr: The payload contains a chunk of the header.
  • Ek: The payload contains a chunk of the encapsulation key.
  • EkCt1Ack: The payload contains a chunk of the encapsulation key, and the sender has completely received ct1.
  • Ct1Ack: No payload, but the sender has completely received ct1.
  • Ct1: The payload contains a chunk of ct1.
  • Ct2: The payload contains a chunk of ct2.
• data (bytes, optional): Erasure code chunk when type is not one of { None, Ct1Ack }

In what follows we will describe messages logically using object notation. Implementations may use a custom compact binary format or a general purpose serialization tool such as Protocol Buffers [6] to encode these messages. In the presence of bandwidth limits, implementers should consider that a custom format may allow larger chunk sizes and correspondingly improve post-compromise security (See Section 3.4).

2.4 Internal Authentication

While messaging protocols such as the Double Ratchet [2] provide ratcheted message authentication through the use of AEAD or explicit MACs on messages, it may be desirable for an SCKA protocol to provide internal authenticity guarantees. We attain this using a Ratcheted Authenticator.

Ratcheted Authenticator state variables

The Ratcheted Authenticator holds the following state:

• root_key: a 32 byte value.
• mac_key: a 32 byte key for use with MAC.

Ratcheted Authenticator functions

The Ratcheted Authenticator offers a function to update the internal state with new entropy as well as functions to compute and verify MACs on ciphertexts and header messages:

def Authenticator.Init(auth_state, epoch, key):
    auth_state = {root_key: '\0'*32, mac_key: None }
    auth_state.Update(epoch, key)

def Authenticator.Update(auth_state, epoch, key):
    auth_state.root_key, auth_state.mac_key
      = KDF_AUTH(auth_state.root_key, key, epoch)

def Authenticator.MacHdr(auth_state, epoch, hdr):
    return MAC(
        auth_state.mac_key,
        PROTOCOL_INFO || ":ekheader" || epoch || hdr,
        MAC_SIZE)

def Authenticator.MacCt(auth_state, epoch, ct):
    return MAC(
        auth_state.mac_key,
        PROTOCOL_INFO || ":ciphertext" || epoch || ct,
        MAC_SIZE)

def Authenticator.VfyHdr(auth_state, epoch, hdr, expected_mac):
    if expected_mac != auth_state.MacHdr(epoch, hdr):
        FAIL

def Authenticator.VfyCt(auth_state, epoch, ct, expected_mac):
    if expected_mac != auth_state.MacCt(epoch, ct):
        FAIL

In the event of a verification failure, protocol participants should not proceed with the ML-KEM Braid session and should negotiate a new ML-KEM Braid session.

2.5 State Machine and Transitions

We describe the protocol as a state machine that transitions from state to state when sending or receiving messages. The states and transitions can be seen in the following figure, which can serve as a helpful reference in the detailed descriptions that follow.

                            (1)
          KeysUnsampled ---------> KeysSampled
               ^                       |
               |                       | (2)
               | (13)                  v
          Ct2Sampled              HeaderSent
            ^    ^                     |
     (11)  /      \  (12)             | (3)
          /        \                   v
  Ct1Acknowledged  EkReceivedCt1Sampled    Ct1Received
          ^        ^                   |
     (8)  |        | (10)             | (4)
          |        |                   v
          +--------+             EkSentCt1Received
               |                       |
          Ct1Sampled                   | (5)
               ^                       v
               | (7)            NoHeaderReceived
               |                       ^
          HeaderReceived               | (6)
               ^                       |
               +-----------------------+

  Transition labels:
  (1)  KeysUnsampled   --Send-->     KeysSampled
  (2)  KeysSampled     --Recv Ct1--> HeaderSent
  (3)  HeaderSent      --Recv Ct1--> Ct1Received
  (4)  Ct1Received     --Recv Ct2--> EkSentCt1Received
  (5)  EkSentCt1Recv   --Recv Ct2--> NoHeaderReceived  [emits key]
  (6)  NoHeaderRecv    --Recv Hdr--> HeaderReceived
  (7)  HeaderReceived  --Send-->     Ct1Sampled         [emits key]
  (8)  Ct1Sampled      --Recv EkCt1Ack--> Ct1Acknowledged
  (9)  Ct1Sampled      --Recv EkCt1Ack+full ek--> Ct2Sampled
  (10) Ct1Sampled      --Recv Ek+full--> EkReceivedCt1Sampled
  (11) Ct1Acknowledged --Recv EkCt1Ack+full--> Ct2Sampled
  (12) EkRecvCt1Sampled --Recv EkCt1Ack--> Ct2Sampled
  (13) Ct2Sampled      --Recv next epoch--> KeysUnsampled

All states of the agents contain at least the following two variables:

• epoch: an unsigned integer identifying the epoch of the key being negotiated.
• auth: an Authenticator object.

The following describes the state of an agent when they are transmitting an encapsulation key and awaiting the corresponding ciphertext. For each state we define the SCKA Send() and Receive() functions.

KeysUnsampled

Represents an agent that is ready to sample a new KEM keypair on the next send event. It carries no additional state.

When sending a message, the KeysUnsampled agent samples a new keypair, starts sending a header message, and transitions into the KeysSampled state. The KeysUnsampled agent ignores all messages it receives:

def KeysUnsampled.Send(state):
  # Generate keypair and header
  (dk, ek_seed, ek_vector) = KEM.KeyGen()
  hek = SHA3-256(ek_seed || ek_vector)
  header = ek_seed || hek
  mac = state.auth.MacHdr(state.epoch, header)
  header_encoder = Encode(header || mac)

  # Generate message
  chunk = header_encoder.next_chunk()
  msg = {epoch: state.epoch, type: Hdr, data: chunk}

  # Update state
  # Transition (1)
  state = KeysSampled(
    state.epoch,
    state.auth,
    dk,
    ek_seed,
    ek_vector,
    hek,
    header_encoder)

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def KeysUnsampled.Receive(state, msg):
  # No action taken
  output_key = None
  receiving_epoch = state.epoch - 1
  return (receiving_epoch, output_key)

KeysSampled

Represents an agent that has sampled a KEM keypair and is sending the header. Additional state includes:

• dk: a KEM decapsulation key
• ek_vector: vector part of a KEM encapsulation key
• header_encoder

The KeysSampled agent sends chunks of the header. When it receives a message of type Ct1 it knows that the other party has received the complete header so it transitions into the HeaderSent state, in which it will begin sending chunks of ek_vector:

def KeysSampled.Send(state):
  # Generate next header chunk
  chunk = state.header_encoder.next_chunk()
  msg = {epoch: state.epoch, type: Hdr, data: chunk}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def KeysSampled.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == Ct1:
      # Initialize ct1 decoder and ek encoder
      ct1_decoder = Decoder.new(KEM.CT1_SIZE)
      ct1_decoder.add_chunk(msg.data)
      ek_encoder = Encode(state.ek_vector)

      # Update state
      # Transition (2)
      state = HeaderSent(
        state.epoch,
        state.auth,
        state.dk,
        ct1_decoder,
        ek_encoder)

  return (receiving_epoch, output_key)

HeaderSent

Represents an agent that has completed sending a header, is currently sending an ek_vector, and is receiving chunks of ct1. Additional state includes:

• dk: a KEM decapsulation key
• ct1_decoder
• ek_encoder

In the HeaderSent state, an agent sends chunks of its ek_vector. When receiving a message of type Ct1 for the current epoch, if it has enough chunks to decode the incoming ct1, it transitions to the Ct1Received state:

def HeaderSent.Send(state):
  # Generate next ek_vector chunk
  chunk = state.ek_encoder.next_chunk()
  msg = {epoch: state.epoch, type: Ek, data: chunk}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def HeaderSent.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == Ct1:
      # Add chunk to decoder
      state.ct1_decoder.add_chunk(msg.data)

      # Check if ct1 is complete
      if state.ct1_decoder.has_message():
          ct1 = state.ct1_decoder.message()

          # Update state
          # Transition (3)
          state = Ct1Received(
            state.epoch,
            state.auth,
            state.dk,
            ct1,
            state.ek_encoder)

  return (receiving_epoch, output_key)

Ct1Received

Represents an agent that has completely received ct1 and is still sending chunks of ek_vector. Additional state includes:

• dk: a KEM decapsulation key
• ct1: The compressed public key part of a KEM ciphertext
• ek_encoder

In the Ct1Received state an agent sends chunks of the ek_vector until it receives a chunk of ct2. At that point it knows ek_vector has been received so it transitions into the EkSentCt1Received state:

def Ct1Received.Send(state):
  # Generate next ek_vector chunk with acknowledgment
  chunk = state.ek_encoder.next_chunk()
  msg = {epoch: state.epoch, type: EkCt1Ack, data: chunk}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def Ct1Received.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == Ct2:
      # Initialize ct2 decoder
      ct2_decoder = Decoder.new(KEM.CT2_SIZE + MAC_SIZE)
      ct2_decoder.add_chunk(msg.data)

      # Update state
      # Transition (4)
      state = EkSentCt1Received(
        state.epoch,
        state.auth,
        state.dk,
        state.ct1,
        ct2_decoder)

  return (receiving_epoch, output_key)

EkSentCt1Received

Represents an agent that has received ct1, sent ek, and is receiving chunks of ct2. Additional state includes:

• dk: a KEM decapsulation key
• ct1: The compressed public key part of a KEM ciphertext
• ct2_decoder

In the EkSentCt1Received state an agent doesn't send any data to the other party and it receives chunks of ct2. Once ct2 is received, it verifies the MAC, decapsulates the secret, emits the key, and transitions to the NoHeaderReceived state to wait for the other party to begin sending an encapsulation key for the next epoch:

def EkSentCt1Received.Send(state):
  # No data to send
  msg = {epoch: state.epoch, type: None}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def EkSentCt1Received.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == Ct2:
      # Add chunk to decoder
      state.ct2_decoder.add_chunk(msg.data)

      # Check if ct2 is complete
      if state.ct2_decoder.has_message():
          ct2_with_mac = state.ct2_decoder.message()
          ct2 = ct2_with_mac[:KEM.CT2_SIZE]
          mac = ct2_with_mac[KEM.CT2_SIZE:]

          # Decapsulate shared secret
          ss = KEM.Decaps(state.dk, state.ct1, ct2)
          ss = KDF_OK(ss, state.epoch)

          # Update authenticator and verify MAC
          state.auth.Update(state.epoch, ss)
          state.auth.VfyCt(state.epoch, state.ct1 || ct2, mac)

          # Prepare for next epoch
          header_decoder = Decoder.new(KEM.HEADER_SIZE + MAC_SIZE)

          # Update state and return key
          # Transition (5)
          state = NoHeaderReceived(
            state.epoch + 1,
            state.auth,
            header_decoder)
          output_key = (state.epoch - 1, ss)

  return (receiving_epoch, output_key)

The following describes the state of an agent when they are transmitting a ciphertext in response to an encapsulation key.

NoHeaderReceived

Represents an agent that is receiving a header. Additional state includes:

• header_decoder

In the NoHeaderReceived state an agent receives chunks of the header. Once the header has been completely received, it transitions to the HeaderReceived state, but does not sample the ciphertext yet:

def NoHeaderReceived.Send(state):
  # No data to send
  msg = {epoch: state.epoch, type: None}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def NoHeaderReceived.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == Hdr:
      # Add chunk to decoder
      state.header_decoder.add_chunk(msg.data)

      # Check if header is complete
      if state.header_decoder.has_message():
          header_with_mac = state.header_decoder.message()
          header = header_with_mac[:64]
          mac = header_with_mac[64:]
          ek_seed = header[:32]
          hek = header[32:]

          # Verify header MAC
          state.auth.VfyHdr(state.epoch, header, mac)

          # Prepare ek_vector decoder
          ek_decoder = Decoder.new(KEM.EK_SIZE)

          # Update state
          # Transition (6)
          state = HeaderReceived(
            state.epoch,
            state.auth,
            ek_seed,
            hek,
            ek_decoder)

  return (receiving_epoch, output_key)

HeaderReceived

Represents an agent that has received a header and is prepared to sample a new ct1 on the next send. Additional state includes:

• ek_seed: seed of a KEM encapsulation key
• hek: SHA3 hash of ek_seed || ek_vector
• ek_decoder

In the HeaderReceived state an agent is ready to sample a ciphertext when asked to send. When it does this, it computes the encapsulated shared secret for this epoch and returns it to the caller. While it has an ek_decoder prepared, it will not receive any ek_vector chunks until after it has sent a ct1 message - and then it will have transitioned out of this state. So the Receive function is a no-op:

def HeaderReceived.Send(state):
  # Generate shared secret and ct1
  (encaps_secret, ct1, ss) = KEM.Encaps1(state.ek_seed, state.hek)
  ss = KDF_OK(ss, state.epoch)

  # Update authenticator
  state.auth.Update(state.epoch, ss)

  # Encode ct1 for transmission
  ct1_encoder = Encode(ct1)
  chunk = ct1_encoder.next_chunk()
  msg = {epoch: state.epoch, type: Ct1, data: chunk}

  # Update state
  # Transition (7)
  state = Ct1Sampled(
    state.epoch,
    state.auth,
    state.ek_seed,
    state.hek,
    encaps_secret,
    ct1,
    ct1_encoder,
    state.ek_decoder)

  # Return values
  output_key = (state.epoch, ss)
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def HeaderReceived.Receive(state, msg):
  # No action taken
  output_key = None
  receiving_epoch = state.epoch - 1
  return (receiving_epoch, output_key)

Ct1Sampled

Represents an agent that has received a header, has sampled ct1, and is sending it in chunks. Additional state includes:

• ek_seed: seed of a KEM encapsulation key
• hek: SHA3 hash of ek_seed || ek_vector
• encaps_secret: the secret material used to encapsulate a KEM ciphertext
• ct1: The compressed public key part of a KEM ciphertext
• ct1_encoder
• ek_decoder

The Ct1Sampled state has the most complex transition possibilities. In this state an agent is receiving chunks of ek_vector and sending chunks of ct1. If it receives all of ek_vector before receiving an acknowledgment that ct1 was received, it will transition to EkReceivedCt1Sampled. On the other hand, if it receives an acknowledgment that ct1 was received before ek_vector has been completely received, it will transition to Ct1Acknowledged. If this agent both receives an acknowledgment for Ct1 and receives the last chunk of ek_vector in a single receive call, it will compute ct2 and transition to Ct2Sampled:

def Ct1Sampled.Send(state):
  # Generate next ct1 chunk
  chunk = state.ct1_encoder.next_chunk()
  msg = {epoch: state.epoch, type: Ct1, data: chunk}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def Ct1Sampled.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == Ek:
      # Add ek_vector chunk
      state.ek_decoder.add_chunk(msg.data)

      # Check if ek_vector is complete
      if state.ek_decoder.has_message():
          ek_vector = state.ek_decoder.message()

          # Verify ek_vector integrity
          if SHA3-256(state.ek_seed || ek_vector) != state.hek:
              raise Error("EK integrity check failed")

          # Update state
          # Transition (10)
          state = EkReceivedCt1Sampled(
            state.epoch,
            state.auth,
            state.encaps_secret,
            state.ct1,
            state.ek_seed,
            ek_vector,
            state.ct1_encoder)

  elif msg.epoch == state.epoch and msg.type == EkCt1Ack:
      # Add ek_vector chunk (with acknowledgment)
      state.ek_decoder.add_chunk(msg.data)

      # Check if ek_vector is complete
      if state.ek_decoder.has_message():
          ek_vector = state.ek_decoder.message()

          # Verify ek_vector integrity
          if SHA3-256(state.ek_seed || ek_vector) != state.hek:
              raise Error("EK integrity check failed")

          # Complete encapsulation
          ct2 = KEM.Encaps2(
            state.encaps_secret, state.ek_seed, ek_vector)
          mac = state.auth.MacCt(state.epoch, state.ct1 || ct2)
          ct2_encoder = Encode(ct2 || mac)

          # Update state
          # Transition (9)
          state = Ct2Sampled(state.epoch, state.auth, ct2_encoder)
      else:
          # Update state
          # Transition (8)
          state = Ct1Acknowledged(
            state.epoch,
            state.auth,
            state.encaps_secret,
            state.ek_seed,
            state.hek,
            state.ct1,
            state.ek_decoder)

  return (receiving_epoch, output_key)

EkReceivedCt1Sampled

Represents an agent that has received an encapsulation key and is still sending ct1 in chunks. Additional state includes:

• encaps_secret: the secret material used to encapsulate a KEM ciphertext
• ct1: The compressed public key part of a KEM ciphertext
• ek_seed
• ek_vector
• ct1_encoder

In the EkReceivedCt1Sampled state an agent sends chunks of ct1 and awaits an acknowledgment that it has been received. When that acknowledgment comes, it computes ct2 and transitions to the Ct2Sampled state:

def EkReceivedCt1Sampled.Send(state):
  # Generate next ct1 chunk
  chunk = state.ct1_encoder.next_chunk()
  msg = {epoch: state.epoch, type: Ct1, data: chunk}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def EkReceivedCt1Sampled.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == EkCt1Ack:
      # Complete encapsulation
      ct2 = KEM.Encaps2(
        state.encaps_secret, state.ek_seed, state.ek_vector)
      mac = state.auth.MacCt(state.epoch, state.ct1 || ct2)
      ct2_encoder = Encode(ct2 || mac)

      # Update state
      # Transition (12)
      state = Ct2Sampled(state.epoch, state.auth, ct2_encoder)

  return (receiving_epoch, output_key)

Ct1Acknowledged

Represents an agent that has completed sending ct1 but is still receiving chunks of ek_vector. Additional state includes:

• ek_seed: seed of a KEM encapsulation key
• hek: SHA3 hash of ek_seed || ek_vector
• encaps_secret: the secret material used to encapsulate a KEM ciphertext
• ct1: The compressed public key part of a KEM ciphertext
• ek_decoder

In the Ct1Acknowledged state an agent receives chunks of an incoming ek_vector. Once this has been completely received, it can compute ct2 and transition to the Ct2Sampled state:

def Ct1Acknowledged.Send(state):
  # No data to send
  msg = {epoch: state.epoch, type: None}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def Ct1Acknowledged.Receive(state, msg):
  output_key = None
  receiving_epoch = state.epoch - 1

  if msg.epoch == state.epoch and msg.type == EkCt1Ack:
      # Add ek_vector chunk
      state.ek_decoder.add_chunk(msg.data)

      # Check if ek_vector is complete
      if state.ek_decoder.has_message():
          ek_vector = state.ek_decoder.message()

          # Verify ek_vector integrity
          if SHA3-256(state.ek_seed || ek_vector) != state.hek:
              raise Error("EK integrity check failed")

          # Complete encapsulation
          ct2 = KEM.Encaps2(
            state.encaps_secret, state.ek_seed, ek_vector)
          mac = state.auth.MacCt(state.epoch, state.ct1 || ct2)
          ct2_encoder = Encode(ct2 || mac)

          # Update state
          # Transition (11)
          state = Ct2Sampled(state.epoch, state.auth, ct2_encoder)

  return (receiving_epoch, output_key)

Ct2Sampled

Represents an agent that has completed sending ct1, received ek_vector, and is sending ct2. Additional state includes:

• ct2_encoder

In the Ct2Sampled state an agent sends chunks of ct2 and waits for a message from the next epoch. Once a message from the next epoch is received, it transitions to the KeysUnsampled state and prepares to start sending a new encapsulation key:

def Ct2Sampled.Send(state):
  # Generate next ct2 chunk
  chunk = state.ct2_encoder.next_chunk()
  msg = {epoch: state.epoch, type: Ct2, data: chunk}

  # Return values
  output_key = None
  sending_epoch = state.epoch - 1
  return (msg, sending_epoch, output_key)

def Ct2Sampled.Receive(state, msg):
  output_key = None

  if msg.epoch == state.epoch + 1:
      # Next epoch has begun
      # Transition (13)
      state = KeysUnsampled(state.epoch + 1, state.auth)

  receiving_epoch = state.epoch - 1
  return (receiving_epoch, output_key)

2.6 Initialization

We initialize Alice and Bob's protocol state using a preshared secret that may come from a handshake protocol such as PQXDH [7]. Alice is initialized to begin sending an encapsulation key header, while Bob is initialized to expect to receive that header:

def InitAlice(shared_secret):
    epoch = 1
    auth = Authenticator.Init(epoch, shared_secret)
    return KeysUnsampled(epoch, auth)

def InitBob(shared_secret):
    epoch = 1
    auth = Authenticator.Init(epoch, shared_secret)
    header_decoder = Decoder.new(KEM.HEADER_SIZE + MAC_SIZE)
    return NoHeaderReceived(epoch, auth, header_decoder)

With this initialization, Alice and Bob will always be able to make forward progress as long as fresh messages are delivered. The graph of possible state transitions can be seen in the figure below.

           (KeysUnsampled, NoHeaderReceived)
                        |
                        v
           (KeysSampled, NoHeaderReceived)
                        |
                        v
            (KeysSampled, HeaderReceived)
                        |
                        v
              (KeysSampled, Ct1Sampled)
                        |
                        v
     +----------(HeaderSent, Ct1Sampled)----------+
     |                  |                          |
     v                  v                          v
(HeaderSent,    (Ct1Received, Ct1Sampled)   (HeaderSent,
 EkRecvCt1Samp)     |          |          EkRecvCt1Samp)
     |              |          |               |
     |              v          v               |
     |  (Ct1Received,   (Ct1Received,          |
     |   Ct1Acknowledged) EkRecvCt1Samp)       |
     |        |              |                 |
     |        v              v                 |
     +----->(Ct1Received, Ct2Sampled)<---------+
                        |
                        v
           (EkSentCt1Received, Ct2Sampled)
                        |
                        v
           (NoHeaderReceived, Ct2Sampled)
                        |
                        v
           (NoHeaderReceived, KeysUnsampled)

  In each tuple, Alice's state is on the left and
  Bob's state is on the right. At the end of this
  process, Alice and Bob will have switched states
  and will have advanced one epoch.