Repository navigation
kem: from_seed and generate_keypair use unnecessary memory #2482
Description
The methods from_seed and generate_keypair both return a Kem::DecapsulationKey and Kem::EncapsulationKey. However, DecapsulationKey already must impl Decapsulator, which returns a &Kem::EncapsulationKey. Meaning the decap key already owns a copy of the encapsulation key! In other words: the encapsulation key output of from_seed and generate_keypair is guaranteed to be redundant. Since this value is measured in the kilobytes, this is no small overhead.
Proposed fix: from_seed should just return a DecapsulationKey. And it's less clear what to do about generate_keypair. Maybe it gets deleted and replaced with generate_decapsulation_key? Seems invasive.
Activity
tarcieri commentedon Aug 10, 2026
Yeah, originally I went down the path you're suggesting then ended up adding back some "keypair"-like functionality when incorporating some ideas from the various bespoke traits the individual KEM crates provided.
Users have the option of either approach right now, though clearly one is much worse on the stack than the other.
I guess my main motivation was people seem really, really used to thinking this way and don't quite get the idea that a decapsulation key should always have an associated encapsulation key which it knows a priori (see the
Decapsulatortrait). I was torn on it too due to the stack usage (possibly mentioning it in one of my commit messages, not sure).It already somewhat duplicates
KeyInit, though we don't currently bound on it inDecapsulatoror(Try)Decapsulate. We could potentially add such a bound in the next breaking release. That assumes initialization from a seed is always infallible and that all constructions support seeds. I guess we could not bound on it and only implKeyInitfor constructions that do support infallible initialization.One problematic construction which violates this is
dhkem, which needs to use(Try)KeyInit.We could add a bound on the
Generatetrait in e.g.Decapsulator, especially asrand_coreis a hard dependency. All of the decapsulation key types should already impl it, I think?rozbb commentedon Aug 10, 2026
I couldn’t figure out how to do it any other way. Specifically I’m running benchmarks for keygen and I would like to not measure the cost of the ek clone. How would I do that using the KEM API?
tarcieri commentedon Aug 11, 2026
@rozbb what specifically are you trying to do? For keygen,
Kem::DecapsulationKeycurrently bounds onGenerate. For initializing from a seed, you'll need to bound onKeyInit.rozbb commentedon Sep 3, 2026
What I was trying to do was define an interface for my KEM that permitted an end user to make an sk without adding copy overhead. I think KeyInit fits the bill, though. Sorry for the noise
tarcieri commentedon Sep 4, 2026
I'd like to keep this one open actually. I agree the interface is needlessly inefficient. The decapsulator should generally already have the encapsulation key allocated, so these APIs that return keypairs are needlessly inefficient because they make a copy of the encapsulation key.