kem: `from_seed` and `generate_keypair` use unnecessary memory

[rozbb]

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.

[tarcieri]

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 Decapsulator trait). I was torn on it too due to the stack usage (possibly mentioning it in one of my commit messages, not sure).

from_seed should just return a DecapsulationKey

It already somewhat duplicates KeyInit, though we don't currently bound on it in Decapsulator or (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 impl KeyInit for constructions that do support infallible initialization.

One problematic construction which violates this is dhkem, which needs to use (Try)KeyInit.

And it's less clear what to do about generate_keypair

We could add a bound on the Generate trait in e.g. Decapsulator, especially as rand_core is a hard dependency. All of the decapsulation key types should already impl it, I think?

[rozbb]

Users have the option of either approach right now

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]

@rozbb what specifically are you trying to do? For keygen, Kem::DecapsulationKey currently bounds on Generate. For initializing from a seed, you'll need to bound on KeyInit.