Working on a pure-Rust ML-KEM implementation for Orion forced me to confront the peculiarities of what the FIPS-203 standard allows in terms of storing private decapsulation keys. According to the standard, you may store:

  1. The seed d||z, which is used to derive both the private decapsulation key and its public counterpart.
  2. The serialized form of the private decapsulation key, which includes the public key, a hash thereof, and the FO-transform secret z.

As pointed out by Sophie Schmieg in the excellent paper “Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK” and in her blog post “Unbindable Kemmy Schmidt”, option 2 has several disadvantages when it comes to binding the shared secret k to the ciphertext (MAL-BIND-K-CT) and to the encapsulation key (MAL-BIND-K-PK). While both of these models require an attacker to have access to the private decapsulation key—at which point it’s arguably “game over” anyway—it still seems worthwhile to design an ML-KEM API that minimizes hidden assumptions and potential pitfalls.

This post serves as a brain dump of how I’ve been thinking about designing an API that accounts for these concerns.

I strongly recommend reading the well-written paper and blog post linked above, but here’s a short summary: storing decapsulation keys as seeds not only requires as little as 64 bytes (compared to the 3168-byte serialized ML-KEM-1024 key) but also ensures the scheme is MAL-BIND-K-CT secure. If we want to stay FIPS-compliant, there’s not much we can do in order to provide a MAL-BIND-K-PK secure scheme, as that would require a deterministic generation of z, based on the secret d.

Current API

A user who needs to decapsulate a ciphertext will always hold a decapsulation key, regardless of whether they choose option 1 or 2. However, they are not always guaranteed to have the seed because the seed is fed into an XOF to derive the actual decapsulation and encapsulation key pair. As a result, it is impossible to “go back” and derive the seed from the decapsulation key.

One possible design is to store an optional seed within the key object:

DecapsulationKey { .. Option<Seed> }

However, this is awkward to test, and it raises a usability issue: how do we expect users to store private keys as seeds if there’s a function get_seed() -> Option<Seed> that can return None, while another function always returns the serialized key bytes get_bytes() -> &[u8]?

A more sensible approach is to have two distinct types:

KeyPair::generate() -> Self
KeyPair::from_seed(seed) -> Self
KeyPair::from_key(seed, DecapsulationKey) -> Self
KeyPair::to_seed() -> Seed

DecapsulationKey::unchecked_from_bytes()
DecapsulationKey::to_public() -> EncapsulationKey

A DecapsulationKey object can only be created from raw bytes using unchecked_from_bytes(), a name intentionally chosen to signal potential risks (not MAL-BIN-K-CT secure). The documentation will clarify that this method skips certain checks (though it still includes the “Decapsulation input check” from FIPS-203, section 7.3).

DecapsulationKey also does not have any export function, where a user can export the raw bytes. This is because, in order for users to import and use existing keys, generated by other libraries, DecapsulationKey will need the decap() functionality. Since the KeyPair generates a pair of DecapsulationKey/EncapsulationKey, they could simply circumvent the missing DecapsulationKey::generate(), by using KeyPair to generate new keys and export them later via DecapsulationKey directly.

As a result, any new private decapsulation keys generated using this approach must use seed-based storage.

A KeyPair is always guaranteed to have a seed, and the seed is the only thing that can be exported as raw bytes for storage. Its creation is restricted to generate() or from_seed(seed).

If a user wishes to store both a seed and a DecapsulationKey, they can use:

KeyPair::from_key(seed, DecapsulationKey)

This allows us to run all consistency checks from FIPS-203, section 7.1, ensuring MAL-BIND-K-CT security. If you’re asking yourself, why anyone would do this, if the same can be accomplished with just the seed in from_seed(seed), then that’s exactly the point => just use the seed.

I’m still debating whether to include KeyPair::from_key(seed, DecapsulationKey), as I find it hard to imagine a scenario where someone has the seed but also wants to verify that a DecapsulationKey, derived from the same seed, has not been tampered with. If you have the seed, that’s all you need.