kem: allow calculating encapsulation keys instead of borrowing

[tarcieri]

Eagerly calculating entire keypairs at a time, particularly for post-quantum algorithms that use relatively large keys, uses up a lot of stack space. This is particularly problematic for no_alloc users who can't easily shove the relevant types in a Box.

Decapsulator::encapsulation_key currently enforces that the decapsulator eagerly compute the relevant encapsulation key and make it always borrowable.

In RustCrypto/signatures#1261 ml-dsa was changed to use signature::Keypair instead of signature::KeypairRef in order to relieve stack pressure. Handling these kind of use cases is exactly why there are two traits to handle computing versus borrowing, with a blanket impl of the former for the latter that links them.

That isn't true of kem though, where Decapsulator currently requires borrowing. Though DecapsulatorRef is probably not a good name. Regardless, it would be good to either change Decapsulator to allow computing the EncapsulationKey on the fly, or have a pair of traits where one preserves the current behavior and the other permits OTF calculation.

cc @baloo @rozbb

[rozbb]

I agree having a trait that returns an owned encapsulation key is a natural solution. Silly thought: how necessary is this method at all? If a function really needs the encap key for some reason, can’t they just take the encap key as another arg? Or else take a 32B seed and do a full keypair generation from it?

[tarcieri]

Without a trait to obtain an encapsulation key, you’ll never have one to begin with

[baloo]

This is mostly an issue with ml-kem which has a large matrix (and x-wing which is a consumer of ml-kem).

I've played a bit with that idea, but the DecapsulationKey still needs to own the EncryptionKey:
https://github.com/RustCrypto/KEMs/blob/22f594d4ce1e8fab8170659a6050c92b72f5d12d/ml-kem/src/decapsulation_key.rs#L154-L160

And inherently two copies of the matrix. Without a significant rewrite, which would steer away from a reference implementation, I don't see how we could do that.

[rozbb]

It only needs to hold the hash of the encapsulation key, no?

[baloo]

it needs the hash:

  let (Kp, rp) = G(&[&mp, &self.ek.h()]);

and it's used two lines below:

 let cp = self.ek.ek_pke().encrypt(&mp, &rp);

[rozbb]

Ah right right. I guess theoretically the decap key could recompute the encap key every time it’s used, but that’d be odd, and it prob doesn’t help if the goal is to reduce the max stack space.

So maybe the status quo is the correct thing after all?

[tarcieri]

I still think there's value in having both options, but it does seem this can't immediately help ml-kem

[rozbb]

All the standardized PQ KEMs have this structure fwiw. The Fujisaki-Okamoto transform requires that decapsulators re-encrypt the plaintext.

[tarcieri]

Alright, we can leave it as-is