Comments on KEM traits

[bifurcation]

As part of the work to add an ML-KEM implementation, I took a look at the KEM traits in this repo (in the kem directory). Given that crates.io shows only a few dependents, I thought some comments might still be acceptable. Mostly fairly minor things.

• The core point in this API is EncappedKey, in the sense that that's the type that knows about all of the types involved in this KEM. That seems odd to me.

  • The encapsulated key seems more like a "plain data" type than an "intelligent" type.
  • It's not clear why the encapped key needs to know the public key types anyway, since once you have an encapped key, you mainly want to know how to decapsulate it.
  • I would refactor this to be more like Signer<S> and Verifier<S>, where the things the two sides need to agree on are in the generic parameters.
  • The analogy here would be Encapsulator<EK, SS> and Decapsulator<EK, SS>, since the encapsulation key and shared secret are the two things that the sender and receiver need to agree on.
  • That means it will be up to implementors of the traits to define EK and SS, but these are just byte arrays.

• Encapsulator::try_encap method is incorrect to take a public key argument. self should be represent the encapsulation key, just as in Decapsulator::try_decap, self represents the decapsulation key.

• I would drop the AuthDecapsulator trait for now. It's inappropriate to have that without a corresponding AuthEncapsulator trait. And AFAIK the only known implementation of these operations is DHKEM, so it doesn't seem worth generalizing right now.

• In Encapsulator::try_encap, you don't need to be generic over the RNG type, you can just take &mut impl CryptoRngCore, as in RandomizedDigestSigner.

• Unless you're going to provide an infallible version like Signer does (try_sign vs. sign), I would remove the try_ from the encap/decap methods.

• I note that there are no as_bytes / from_bytes methods on the traits for encapsulation / decapsulation keys. That seems consistent with other traits in this repo, but just wanted to check it was intended, since at least for encapsulation keys, one will want to ship them around.

• My sense is that there is a general trend toward using more functional names for keys, so for example, "verifying key" or "encapsulation key" instead of "public key" / "signing key" or "decapsulation key" instead of "private key". That seems like a pattern we should follow here, e.g., in the decapsulation key argument to Encapsulator::try_encaps.

• I would generally avoid shortening "encapsulate" and "decapsulate" for clarity. So for example EncapsulatedKey instead of EncappedKey and try_decapsulate instead of try_decap.

• While I'm not sure there's a really standard spelling here, the "-or" ending to Encapsulator and Decapsulator looks odd to me, and inconsistent with other crates in this repo, which use "-er".

  • Personally, I would rather use verbs Encapsulate / Decapsulate, in parallel with Copy, Clone, etc.
  • The precedent in other crates in this repo seems mixed. On the one hand, Signer, Verifier, PasswordHasher. On the other hand, Aead, KeyInit, Digest, Mac.

• The kem traits are not linked from the crypto façade, but this seems to not be unique.

In summary, I would probably simplify this interface down to two traits:

pub struct Error; // as now

trait Encapsulate<EK, SS> {
    fn encapsulate(&self, rng: &mut impl CryptoRngCore) -> Result<(EK, SS), Error>;
}

trait Decapsulate<EK, SS> {
    fn decapsulate(&self, enc: &EK) -> Result<SS, Error>;
}

[tarcieri]

While I'm not sure there's a really standard spelling here, the "-or" ending to Encapsulator and Decapsulator looks odd to me, and inconsistent with other crates in this repo, which use "-er".

FWIW we do use -or in quite a few places: the aead::stream module uses Encryptor/Decryptor (per the STREAM paper), and the rsa traits also use Encryptor/Decryptor: https://docs.rs/rsa/latest/rsa/traits/index.html

We do use Signer/Verifier in signature but that's largely because Signor/Verifior aren't words.

I would probably suggest using Encapsulator/Decapsulator since using -er for these seems unusual at best.

[rozbb]

Thanks for the detailed comments! I agree it was weird to hinge everything on EncappedKey. I think the reason was, after a few iterations, that it was the only reasonable way to make the Auth- versions of the traits be consistent with the non-auth versions. Or something like that. But if Auth- is removed, the problem should go away. I'll take a crack at this

[bifurcation]

FWIW, I think you could do something similar for the Auth- versions, something like:

trait AuthEncapsulator<Encap, DK, SS> {
    fn auth_encapsulate(&self, rng: &mut impl CryptoRngCore, from: &DK) -> Result<(Encap, SS), Error>;
}

trait AuthDecapsulator<Encap,  EK, SS> {
    fn auth_decapsulate(&self, enc: &Encap, from: &EK) -> Result<SS, Error>;
}

[rozbb]

I think Auth- even goes away if you're willing to put the identity keys in Self. Regardless though we probably don't need it for now

[conradludgate]

• I would refactor this to be more like Signer<S> and Verifier<S>, where the things the two sides need to agree on are in the generic parameters.

• The analogy here would be Encapsulator<EK, SS> and Decapsulator<EK, SS>, since the encapsulation key and shared secret are the two things that the sender and receiver need to agree on.

I think it was a mistake in retrospect for Signer to be generic. Are there any examples of any key types that implement signer in more than one way to produce different signature outputs?

However, if we are going this route, I personally think the traits should be

trait Encapsulator<EK> {
    type SS;
}

The pair (EncapsulatingKey, EncapsulatedKey) should be enough to determine the SharedSecret type. Likewise so should the pair (DecapsulatingKey, EncapsulatedKey).

I'd still prefer both of these traits though:

trait Signer { type Signature; }
trait Encapsulator { type EncapsulatedKey; type SharedSecret; }

This generally just helps with inference and if the types don't match it'll still compile fail.

---

On the topic of object safety, associated types lose you nothing. Instead of

dyn Encapsulator<EK, SS>

You have

dyn Encapsulator<EK, SharedSecret = SS>

[tarcieri]

I think it was a mistake in retrospect for Signer to be generic. Are there any examples of any key types that implement signer in more than one way to produce different signature outputs?

Note: these comments apply primarily to the signature crate.

Yes, it comes up all the time. Check out the ecdsa crate: https://docs.rs/ecdsa/0.16.9/ecdsa/struct.SigningKey.html#impl-Signer%3C(Signature%3CC%3E,+RecoveryId)%3E-for-SigningKey%3CC%3E

There are multiple types/formats for serializing ECDSA signatures including IEEE 1363, ASN.1 DER, and types which are parameterized with an additional OID which identifies the digest algorithm used to compute the signature, not to mention it's used with a 2-tuple as a way to compute an associated RecoveryId which can be used to recover the public key from a signature.

RSA is a similar zoo of multitudes of signature formats.

I'm not sure these concerns apply to the kem crate, however.

[conradludgate]

There are multiple types/formats for serializing ECDSA signatures including IEEE 1363, ASN.1 DER, and types which are parameterized with an additional OID which identifies the digest algorithm used to compute the signature, not to mention it's used with a 2-tuple as a way to compute an associated RecoveryId which can be used to recover the public key from a signature.

In theory, the SigningKey could be parameterised instead, and perhaps the tuple recovery key result should not even be an implementation of the trait but an inherent method. However, I concede the original point, it does have some usefulness I cannot deny

[tarcieri]

signature is already at v2.0 and we don't plan on making breaking changes for years.

In theory, the SigningKey could be parameterised instead

That would preclude a SigningKey being usable for multiple/dynamic signature encodings/formats at runtime, which is important for e.g. KMS systems.

(Also, this is all a bit off topic for this thread, except to contrast with KEM use cases)