`hash2curve`: Bringing breaking changes to ease maintainability & usability.

[carloskiki]

There are a few changes I would like to bring to hash2curve, mainly to reduce the amount of code the crate has and make it independent of the elliptic-curve crate.

Motivations

1. Reducing the amount of code is always a plus IMHO - makes the crate more maintainable & approachable.
2. elliptic-curve is almost unused as a dependency, but brings a lot of transitive dependencies (see below for comparison).
3. Some functions use out parameters and I would like to change that where possible (Expander and hash_to_field).

Changes

• Change GroupDigest to something like a Suite trait.

/// A hash to curve suite.
///
/// <https://www.rfc-editor.org/rfc/rfc9380.html#name-suites-for-hashing>
pub trait Suite {
    const ID: &'static str;

    type Point: MapToCurve;
    type SecurityLevel: Unsigned;
    type ExpandMsg: ExpandMsg<Self::SecurityLevel>;

    fn hash_from_bytes(msg: &[&[u8]], dst: &[&[u8]]) -> Option<Self::Point> {
        // ...
    }

    fn encode_from_bytes(msg: &[&[u8]], dst: &[&[u8]]) -> Option<Self::Point> {
        // ...
    }
}

• MapToCurve will be bound by Group instead of CurveArithmetic.
• All places that return elliptic_curve::Result<_> will return Option instead (elliptic_curve::Error was already as ZST).
• Make hash_to_field output Array<F, C> for F: FromOkm and C: ArraySize instead of taking &mut [F] as out parameter.
• Make ExpandMsg return Iterator<Item = u8> instead of an Expander (This may cause a slight performance regression, will be benchmarked before it is added).

Dependency tree with & without elliptic-curve

With elliptic-curve

hash2curve v0.14.0-rc.0
├── digest v0.11.0-rc.0
│   ├── block-buffer v0.11.0-rc.4
│   │   └── hybrid-array v0.3.1
│   │       ├── typenum v1.18.0
│   │       └── zeroize v1.8.1
│   └── crypto-common v0.2.0-rc.3
│       └── hybrid-array v0.3.1 (*)
├── elliptic-curve v0.14.0-rc.10
│   ├── base16ct v0.2.0
│   ├── crypto-bigint v0.7.0-pre.6
│   │   ├── hybrid-array v0.3.1 (*)
│   │   ├── num-traits v0.2.19
│   │   │   [build-dependencies]
│   │   │   └── autocfg v1.5.0
│   │   ├── rand_core v0.9.3
│   │   ├── subtle v2.6.1
│   │   └── zeroize v1.8.1
│   ├── ff v0.14.0-pre.0
│   │   ├── rand_core v0.9.3
│   │   └── subtle v2.6.1
│   ├── group v0.14.0-pre.0
│   │   ├── ff v0.14.0-pre.0 (*)
│   │   ├── rand_core v0.9.3
│   │   └── subtle v2.6.1
│   ├── hybrid-array v0.3.1 (*)
│   ├── rand_core v0.9.3
│   ├── subtle v2.6.1
│   └── zeroize v1.8.1
├── ff v0.14.0-pre.0 (*)
└── subtle v2.6.1

Without:

hash2curve v0.14.0-rc.0
├── digest v0.11.0-rc.0
│   ├── block-buffer v0.11.0-rc.4
│   │   └── hybrid-array v0.3.1
│   │       └── typenum v1.18.0
│   └── crypto-common v0.2.0-rc.3
│       └── hybrid-array v0.3.1 (*)
├── ff v0.14.0-pre.0
│   ├── rand_core v0.9.3
│   └── subtle v2.6.1
├── group v0.14.0-pre.0
│   ├── ff v0.14.0-pre.0 (*)
│   ├── rand_core v0.9.3
│   └── subtle v2.6.1
└── subtle v2.6.1

[daxpedda]

Just my 2¢:

• Change GroupDigest to something like a Suite trait.

We do actually want generic ExpandMsg on a function instead of it being fixed in a associated type. Implementers need this flexibility. Implementing a generic Suite implementer wouldn't work this way because the methods shouldn't and can't really be defined by the user.

I do think changing type K to SecurityLevel is a great improvement. Maybe TargetSecurityLevel to more accurately align with the spec.

• MapToCurve will be bound by Group instead of CurveArithmetic.

I think anything moving us away from CurveArithmetic, which isn't really necessary at all here, is a great improvement.

• All places that return elliptic_curve::Result<_> will return Option instead (elliptic_curve::Error was already as ZST).

I would argue that this is un-Rusty. Option signifies that its possible these methods return nothing, but this isn't right. It is an actual error users have to address somehow.

However, I assume the point here is to drop the elliptic-curve dependency. For that purpose we can define a custom error type in hash2curve. Or maybe move elliptic_curve::Error to crypto_common?

• Make hash_to_field output Array<F, C> for F: FromOkm and C: ArraySize instead of taking &mut [F] as out parameter.

hash_to_field() is an internal method only, despite being pub it is doc(hidden). I actually believe at this point we can go ahead and make it private. The only reason it was public is because earlier drafts of protocols using hash2curve were actually using hash_to_field(), this isn't case anymore. Its only used for testing in curve crates at this point.

• Make ExpandMsg return Iterator<Item = u8> instead of an Expander (This may cause a slight performance regression, will be benchmarked before it is added).

I don't think Rust will ever be able to optimize this away in every scenario because there can be so much run-time logic involved here without fixed sizes.

That said, in reality this isn't going to have any real-world performance effects compared to all the expensive crypto operations happening around all this.

---

I was planning to make a PR soon to remove FromOkm in favor of Reduce which would put another dent into getting rid of elliptic-curve as a dependency.

If I may ask, what exactly is the motivation behind all this? Do you actually have a use-case for using hash2curve without elliptic-curve?

[carloskiki]

We do actually want generic ExpandMsg on a function instead of it being fixed in a associated type. Implementers need this flexibility. Implementing a generic Suite implementer wouldn't work this way because the methods shouldn't and can't really be defined by the user.

From what I understood in RFC9380, the choice of expand_message function should be fixed for a specific Suite. Are there places where that's not the case? I understand that we still need to let users decide their choice of expand_message when they do not want to use a specific suite. The way I initially saw it was that we expose the encode_from_bytes and hash_from_bytes functions generic over all of their parameters, which would look a bit something like this:

pub fn encode_from_bytes<X, K, P>(msg: &[&[u8]], dst: &[&[u8]]) -> Option<P>
where
    X: ExpandMsg<K>,
    P: MapToCurve,
{
    let u = hash_to_field::<X, _, P::FieldElement, U1>(msg, dst)?;
    let q0 = P::map_to_curve(u[0]);
    Some(P::map_to_subgroup(q0))
}

pub fn hash_from_bytes<X, K, P>(msg: &[&[u8]], dst: &[&[u8]]) -> Option<P> {
    // ...
}

If we only expose these free-standing functions, then libraries that implement a hash2curve suite would re-export these functions parameterized over their specific types. The only issue we might have is that this is quite the breaking change, going from GroupDigest to no trait at all - people might complain. That's why we could also introduce the Suite trait along with the free-standing functions.

I would argue that this is un-Rusty. Option signifies that its possible these methods return nothing, but this isn't right. It is an actual error users have to address somehow.

I agree, how about we let ExpandMsg have an Error associated type, and propagate this error instead of defining ours? I will open a PR with this to see what it looks like.

I don't think Rust will ever be able to optimize this away in every scenario because there can be so much run-time logic involved here without fixed sizes.

I don't know nearly enough about llvm to say whether it will or not, but I think it is worth trying because I think it would make the API much nicer. Exander is basically an Iterator<Item = &[u8]> that internally does memcpy into the provided buffer. It would be nice to remove this trait in favor of a primitive like impl Iterator, even if it ends up being impl Iterator<Item = &[u8]>. It makes the thing easier to understand (ExpandMsg generates some bytes based on a msg), and hopefully reduces the API surface while reducing the amount of code.

I was planning to make a PR soon to remove FromOkm in favor of Reduce which would put another dent into getting rid of elliptic-curve as a dependency.

That's fine, arguably Reduce should belong to crypto-bigint, but that's no big deal. Don't block anything you planned because of this, we'll figure it out later.

If I may ask, what exactly is the motivation behind all this? Do you actually have a use-case for using hash2curve without elliptic-curve?

curve25519-dalek currently does not depend on elliptic-curve, and since the crate is only lightly maintained, it would be nice to not have to introduce too much changes to have hash2curve. I personally think that elliptic-curve currently contains too much stuff. Things like PrivateKey, PublicKey, JwkKey, sec1 {de}serialization, etc. are not about elliptic-curves (but that's another thing entirely). The ArithmeticCurve trait is also not the right abstraction in my opinion. It forces implementors to have a full arithmetic suite even though protocols like X25519, X448, etc. don't require them. In the end, either you don't implement the useful trait, or you introduce a bunch of arithmetic that won't be used (more code = more opportunities for vulnerabilities to creep in) just to satisfy a trait bound.

[tarcieri]

arguably Reduce should belong to crypto-bigint

I'm not sure how that would work in such a way it would produce a scalar for a given elliptic curve

curve25519-dalek currently does not depend on elliptic-curve, and since the crate is only lightly maintained, it would be nice to not have to introduce too much changes to have hash2curve

I'm also a maintainer of curve25519-dalek, and happy to help hash2curve get integrated there. It would also be helpful to have more eyes on this PR, especially since there was a fairly major problem that nobody spotted: dalek-cryptography/curve25519-dalek#786

I personally think that elliptic-curve currently contains too much stuff. Things like PrivateKey, PublicKey, JwkKey, sec1 {de}serialization, etc. are not about elliptic-curves (but that's another thing entirely).

Those are elliptic curve private keys, elliptic curve public keys, and elliptic curve serialization formats. They are very much "about elliptic curves".

The ArithmeticCurve trait is also not the right abstraction in my opinion.

I do find it a little funny that after your complaints in RustCrypto/traits#1911 you've wound up proposing something that follows a somewhat similar design pattern to the Curve trait here with Suite.

It forces implementors to have a full arithmetic suite even though protocols like X25519, X448, etc. don't require them.

Yes, the CurveArithmetic trait is extreme overkill for a problem as trivial as Diffie-Hellman. We could have a simpler trait for ECDH, and a blanket impl for the CurveArithmetic case.

[daxpedda]

We do actually want generic ExpandMsg on a function instead of it being fixed in a associated type. Implementers need this flexibility. Implementing a generic Suite implementer wouldn't work this way because the methods shouldn't and can't really be defined by the user.

From what I understood in RFC9380, the choice of expand_message function should be fixed for a specific Suite. Are there places where that's not the case? I understand that we still need to let users decide their choice of expand_message when they do not want to use a specific suite.

I agree, there should be a suite associates with hash2curve. Its just that users should be able to build their own suite. E.g. combining a custom hash with their curve of choice.

The direction itself I think is important to explore because we currently have no way to define a default suite. So if I may layout some requirements:

1. Ability for users to define their own suite (without having to implement hash_from_bytes() and such for existing curves on their own).
2. Ability for curves to expose a default suite, but behind a crate feature. E.g. if the default suite uses SHA2, you should be able to define your own suite without being forced to pull in the sha2 dependency.

The way I initially saw it was that we expose the encode_from_bytes and hash_from_bytes functions generic over all of their parameters, which would look a bit something like this:

pub fn encode_from_bytes<X, K, P>(msg: &[&[u8]], dst: &[&[u8]]) -> Option<P>
where
    X: ExpandMsg<K>,
    P: MapToCurve,
{
    let u = hash_to_field::<X, _, P::FieldElement, U1>(msg, dst)?;
    let q0 = P::map_to_curve(u[0]);
    Some(P::map_to_subgroup(q0))
}

pub fn hash_from_bytes<X, K, P>(msg: &[&[u8]], dst: &[&[u8]]) -> Option<P> {
    // ...
}

If we only expose these free-standing functions, then libraries that implement a hash2curve suite would re-export these functions parameterized over their specific types. The only issue we might have is that this is quite the breaking change, going from GroupDigest to no trait at all - people might complain. That's why we could also introduce the Suite trait along with the free-standing functions.

That would indeed address some of the problems. However this still needs some more design work. E.g. some way for P to enforce the right K. Maybe we can move K to a different trait.

I think it all boils down to the two different pieces we need here:

1. We need a default implementation for a specific curve that is generic over ExpandMsg but includes everything else.
2. We need a way for a specific curve to specify its default ExpandMsg while being able to hide it behind a crate feature.

I believe 1. is already covered by GroupDigest quite properly. 2. could be easily addressed by a second trait.

I don't think Rust will ever be able to optimize this away in every scenario because there can be so much run-time logic involved here without fixed sizes.

I don't know nearly enough about llvm to say whether it will or not, but I think it is worth trying because I think it would make the API much nicer. Exander is basically an Iterator<Item = &[u8]> that internally does memcpy into the provided buffer. It would be nice to remove this trait in favor of a primitive like impl Iterator, even if it ends up being impl Iterator<Item = &[u8]>. It makes the thing easier to understand (ExpandMsg generates some bytes based on a msg), and hopefully reduces the API surface while reducing the amount of code.

I agree, I think that the current Expander API is quite un-rusty and has a lot of rough edges. Quick example: Expander::fill_bytes() has no return value and therefore no way to tell the user how many bytes if at all were written. Maybe it should be returning a Result?

If Iterator<Item = u8> works, then that would be great ofc. However Iterator<Item = &[u8]> wouldn't work because Expander doesn't have an internal buffer nor a pre-specified chunk length to begin with. I would also have no idea how to properly add this.

The current design has a couple of reasons:

• It needs to be allocation free.
• The length passed in expand_message() is determined during run-time. See Experiment: enforce constraints of ExpandMsg on the type level traits#872 (comment).
• It can be used entirely independent of all the other pieces in hash2curve.

So the only ways I know how to fix this:

• Change length passed in expand_message() to a const L, which is currently not possible due to Rust limitations. This would allow us to simply return a fixed-sized buffer users can handle themselves.
• Merge ExpandMsg with hash_to_field(). I have no idea who needs ExpandMsg on its own.

The ArithmeticCurve trait is also not the right abstraction in my opinion. It forces implementors to have a full arithmetic suite even though protocols like X25519, X448, etc. don't require them. In the end, either you don't implement the useful trait, or you introduce a bunch of arithmetic that won't be used (more code = more opportunities for vulnerabilities to creep in) just to satisfy a trait bound.

AFAIK this only does apply to these two curves, who have a x-only coordinate system which isn't able to do full arithmetic and is optimized for DH only. However, DH isn't the only thing these are used for and having a version of the curve being able to do full arithmetic operations still has value. See #1291.

To implement hash2curve for a specific curve, it requires some arithmetic capability. E.g. hash_to_curve() can not be implemented without an addition operator, which neither X25519 or X448 support (AFAIK, I couldn't find anything). CurveArithmetic itself only requires multiplication on top of that, which can be shared between multiple curves as we do in ed448-goldilocks.

Looking at curve25519-dalek, the only piece its missing is affine representations for existing points. These affine representations don't add a whole lot of code around them and partly already exist and just need to be exposed. See dalek-cryptography/curve25519-dalek#769. Again: these things have value on their own already and shouldn't be treated as dead code.

So I'm not entirely convinced CurveArithmetic is too broad. Unless ofc you want to implement only encode_to_curve() for X25519/X448. See again #1291 for how I've done that that there. But I'm not sure about the use-case here.

[carloskiki]

arguably Reduce should belong to crypto-bigint

I'm not sure how that would work in such a way it would produce a scalar for a given elliptic curve

I think the modular module is supposed to handle modular arithmetic. It feels quite natural to house the Reduce trait there - because this trait is about modular reduction. The trait can be implemented over any type, I don't see any issue in implementing it for a Scalar.

curve25519-dalek currently does not depend on elliptic-curve, and since the crate is only lightly maintained, it would be nice to not have to introduce too much changes to have hash2curve

I'm also a maintainer of curve25519-dalek, and happy to help hash2curve get integrated there. It would also be helpful to have more eyes on this PR, especially since there was a fairly major problem that nobody spotted: dalek-cryptography/curve25519-dalek#786

Great, will take a look at this.

I personally think that elliptic-curve currently contains too much stuff. Things like PrivateKey, PublicKey, JwkKey, sec1 {de}serialization, etc. are not about elliptic-curves (but that's another thing entirely).

Those are elliptic curve private keys, elliptic curve public keys, and elliptic curve serialization formats. They are very much "about elliptic curves".

This is unrelated to hash2curve, but let me still address it.

From my understanding, the PublicKey, SecretKey, and JwkEcKey are all types about format serialization and deserialization, just like the sec1 module (and pkcs8).

My whole argument is that format crates should be separate from the elliptic-curve crate. They already are, so why re-expose everything? There is a weak analogy with serde, where if one wants the json format they import serde_json. There is no json feature flag for the serde crate. This brings a few advantages:

• Reduces the versioning hell of always bumping everything when one crate updates.
• Abstraction boundaries are clearly defined.
• Reduces the amount of feature flags.

How I see it is that if one needs to parse a key in the sec1 format, they import the sec1 crate (instead of enabling a feature flag on elliptic-curve). Let's say one generically wants to support any curve that supports the pkcs8 format, they can do something like C::AffinePoint: pkcs8::EncodePrivateKey + pkcs8::DecodePrivateKey.

If we respect these boundaries, then I don't see any benefit of still having a PublicKey type (for example), except that this vocabulary is simpler (than Point and Scalar) for people that are not familiar with elliptic curves (I would hope someone who depends on elliptic-curve knows what Points and Scalars do!). This can also be easily fixed with a bit of documentation, or linked resources.

This is not a simple change, the crates are currently not architectured to support such abstraction boundaries. This is something I'm trying to gradually work towards.

The ArithmeticCurve trait is also not the right abstraction in my opinion.

I do find it a little funny that after your complaints in RustCrypto/traits#1911 you've wound up proposing something that follows a somewhat similar design pattern to the Curve trait here with Suite.

Indeed 😅, although I stated that this is not something I would personally like to see, it does help the transition phase from GroupDigest.

It forces implementors to have a full arithmetic suite even though protocols like X25519, X448, etc. don't require them.

Yes, the CurveArithmetic trait is extreme overkill for a problem as trivial as Diffie-Hellman. We could have a simpler trait for ECDH, and a blanket impl for the CurveArithmetic case.

I think more broadly that CurveArithmetic is tailored to much for ecdsa specifically. Other protocols (e.g., ecies, and ecqv) might also need slightly different traits.

[tarcieri]

It would probably be good to open a separate issue for this, but to respond to this:

How I see it is that if one needs to parse a key in the sec1 format, they import the sec1 crate (instead of enabling a feature flag on elliptic-curve). Let's say one generically wants to support any curve that supports the pkcs8 format, they can do something like C::AffinePoint: pkcs8::EncodePrivateKey + pkcs8::DecodePrivateKey.

Then instead of having one common implementation of PKCS#8 in the elliptic-curve crate, you would have N implementations for N elliptic curves that want to support PKCS#8. It also supports SEC1 private keys, so you would have N implementations of that as well.

That said, the PKCS#8/SEC1 implementations could potentially be moved to NonZeroScalar (which I assume you meant w\ C::AffinePoint), however SecretKey also handles zeroization and avoids leaking the key material through things like Debug, so switching to NonZeroScalar would lose that, since NonZeroScalar may-or-may-not be secret.

If we respect these boundaries, then I don't see any benefit of still having a PublicKey type (for example), except that this vocabulary is simpler (than Point and Scalar) for people that are not familiar with elliptic curves (I would hope someone who depends on elliptic-curve knows what Points and Scalars do!). This can also be easily fixed with a bit of documentation, or linked resources.

PublicKey enforces non-identity points, though with NonIdentity (which didn't exist at the time PublicKey was created) it could be possible to move the common SPKI and SEC1 implementations there.

Regardless, I think it makes sense to have common, generic support for these formats rather than (2 * )N implementations in N elliptic curves.

[tarcieri]

I think more broadly that CurveArithmetic is tailored to much for ecdsa specifically. Other protocols (e.g., ecies, and ecqv) might also need slightly different traits.

I think the main place there has previously been assumptions is around prime order curves, and while there is a PrimeCurve marker trait, there are places generic impls perhaps aren't appropriately bounded by that trait everywhere it's needed. Now that we have ed448-goldilocks in-org as a non-prime order curve, some improvements are being made in that area.

Speaking of ECIES, the ecdh module is a notable example: https://docs.rs/elliptic-curve/0.14.0-rc.10/src/elliptic_curve/ecdh.rs.html#67

This module currently assumes Diffie-Hellman can be implemented generically in terms of scalar multiplication, but if we look at e.g. x25519-dalek: https://github.com/dalek-cryptography/curve25519-dalek/blob/e3c2455/x25519-dalek/src/x25519.rs#L86

...we need to use mul_clamped. So really Diffie-Hellman should be a curve-specific trait, and the prime order curves can share a generic implementation via a blanket impl.

Edit: @carloskiki if you'd like to continue this discussion perhaps RustCrypto/traits#1911 is a more appropriate place

[carloskiki]

I agree, there should be a suite associates with hash2curve. Its just that users should be able to build their own suite. E.g. combining a custom hash with their curve of choice.

The direction itself I think is important to explore because we currently have no way to define a default suite. So if I may layout some requirements:

1. Ability for users to define their own suite (without having to implement `hash_from_bytes()` and such for existing curves on their own).

2. Ability for curves to expose a default suite, but behind a crate feature. E.g. if the default suite uses SHA2, you should be able to define your own suite without being forced to pull in the `sha2` dependency.

Both of these are already covered if we introduce the Suite trait (point 2) and expose the free-standing functions encode_from_bytes and hash_from_bytes (point 1). elliptic curve implementations implement the MapToCurve trait, and some can define a new suite by using a different ExpandMsg or TargetSecurityLevel.

That would indeed address some of the problems. However this still needs some more design work. E.g. some way for P to enforce the right K. Maybe we can move K to a different trait.

I think it all boils down to the two different pieces we need here:

1. We need a default implementation for a specific curve that is generic over `ExpandMsg` _but_ includes everything else.

2. We need a way for a specific curve to specify its default `ExpandMsg` while being able to hide it behind a crate feature.

I believe 1. is already covered by GroupDigest quite properly. 2. could be easily addressed by a second trait.

Perhaps MapToCurve could host the TargetSecurityLevel associated type. I feel like RFC9380 is a bit ambiguous about K (the target security level) which makes this complicated. As they state:

k is an upper bound on the target security level of the suite. A reasonable choice of k is ceil(log2(r) / 2), where r is the order of the subgroup G of the curve E.

So "a reasonable choice" would be to let MapToCurve define K, but at the same time since this is not a requirement it could come from elsewhere in the suite. They also state:

We stress that this parameter is only an upper bound on the security level of the curve and is neither a guarantee nor endorsement of its suitability for a given application. Mathematical and cryptographic advancements may reduce the effective security level for any curve.

So since its an upper bound, I think it would be fine to let the MapToCurve trait define it, as its "ok" for it to not be accurate.

think it all boils down to the two different pieces we need here:

1. We need a default implementation for a specific curve that is generic over ExpandMsg but includes everything else.
2. We need a way for a specific curve to specify its default ExpandMsg while being able to hide it behind a crate feature.

I believe 1. is already covered by GroupDigest quite properly. 2. could be easily addressed by a second trait.

(1) would be covered by MapToCurve, and (2) by the Suite trait, and otherwise the free-standing functions for being generic over ExpandMsg.

I agree, I think that the current Expander API is quite un-rusty and has a lot of rough edges. Quick example: Expander::fill_bytes() has no return value and therefore no way to tell the user how many bytes if at all were written. Maybe it should be returning a Result?

If Iterator<Item = u8> works, then that would be great ofc. However Iterator<Item = &[u8]> wouldn't work because Expander doesn't have an internal buffer nor a pre-specified chunk length to begin with. I would also have no idea how to properly add this.

The current design has a couple of reasons:

* It needs to be allocation free.

* The length passed in `expand_message()` is determined during run-time. See

Iterator would be a good fit to fulfill both point listed. ExpandMsgXmd could easily be transfered to implement Iterator. Since the next digest version does not expose XofReaderCore from ExtendableOutput implementers,there might be some overhead in implementing Iterator for ExpandMsgXof, I will experiment.

To implement hash2curve for a specific curve, it requires some arithmetic capability. E.g. hash_to_curve() can not be implemented without an addition operator, which neither X25519 or X448 support (AFAIK, I couldn't find anything). CurveArithmetic itself only requires multiplication on top of that, which can be shared between multiple curves as we do in ed448-goldilocks.

I think the group traits already supports most of the arithmetic required. This crate does not belong to RustCrypto and looks poorly maintained, but if it was in good shape then I'm not sure we would need CurveArithmetic anymore. Of course we would still need traits like AffineCoordinates that are specific about elliptic curves, and perhaps some Curve trait if we want a type to bundle everything. Let's discuss this more in RustCrypto/traits#1911.

Looking at curve25519-dalek, the only piece its missing is affine representations for existing points. These affine representations don't add a whole lot of code around them and partly already exist and just need to be exposed. See dalek-cryptography/curve25519-dalek#769. Again: these things have value on their own already and shouldn't be treated as dead code.

I tried a bit ago to do this, and the montgomery curve did not have a full AffinePoint nor did it have projective arithmetic. See dalek-cryptography/curve25519-dalek#746.

[daxpedda]

I agree, there should be a suite associates with hash2curve. Its just that users should be able to build their own suite. E.g. combining a custom hash with their curve of choice.
The direction itself I think is important to explore because we currently have no way to define a default suite. So if I may layout some requirements:

1. Ability for users to define their own suite (without having to implement `hash_from_bytes()` and such for existing curves on their own).

2. Ability for curves to expose a default suite, but behind a crate feature. E.g. if the default suite uses SHA2, you should be able to define your own suite without being forced to pull in the `sha2` dependency.

Both of these are already covered if we introduce the Suite trait (point 2) and expose the free-standing functions encode_from_bytes and hash_from_bytes (point 1). elliptic curve implementations implement the MapToCurve trait, and some can define a new suite by using a different ExpandMsg or TargetSecurityLevel.

Yes, this can be addressed through the free-standing functions.

However, I'm not sure what the advantage here is over Suite relying on GroupDigest. This way the functions aren't free-standing anymore but are found on the curve label, which imo is an improvement, and users won't have write any extra code or find the right function to implement Suite::hash_from_bytes().

That would indeed address some of the problems. However this still needs some more design work. E.g. some way for P to enforce the right K. Maybe we can move K to a different trait.
I think it all boils down to the two different pieces we need here:

1. We need a default implementation for a specific curve that is generic over `ExpandMsg` _but_ includes everything else.

2. We need a way for a specific curve to specify its default `ExpandMsg` while being able to hide it behind a crate feature.

I believe 1. is already covered by GroupDigest quite properly. 2. could be easily addressed by a second trait.

Perhaps MapToCurve could host the TargetSecurityLevel associated type. I feel like RFC9380 is a bit ambiguous about K (the target security level) which makes this complicated. As they state:

k is an upper bound on the target security level of the suite. A reasonable choice of k is ceil(log2(r) / 2), where r is the order of the subgroup G of the curve E.

So "a reasonable choice" would be to let MapToCurve define K, but at the same time since this is not a requirement it could come from elsewhere in the suite. They also state:

We stress that this parameter is only an upper bound on the security level of the curve and is neither a guarantee nor endorsement of its suitability for a given application. Mathematical and cryptographic advancements may reduce the effective security level for any curve.

So since its an upper bound, I think it would be fine to let the MapToCurve trait define it, as its "ok" for it to not be accurate.

The target security level is only relevant for us because ExpandMsgXof is using it to produce specific output. When the spec talks about how to choose a target security level, its talking about how it chose or how users should chose a target security level for a curve.

So for a curve, the target security level should not change, even if the suite might. There might be some very strange use-case for it in the future, but I think we should stick to the spec until we find a justifiable reason to let users modify the target security level.

Talking more about practice here: if you take a look at this example for an OPRF implementation we want users to easily be able to pass their preferred hash. Letting them have to choose K doesn't provide an advantage here AFAICT, but increases the complexity.

Looking at curve25519-dalek, the only piece its missing is affine representations for existing points. These affine representations don't add a whole lot of code around them and partly already exist and just need to be exposed. See dalek-cryptography/curve25519-dalek#769. Again: these things have value on their own already and shouldn't be treated as dead code.

I tried a bit ago to do this, and the montgomery curve did not have a full AffinePoint nor did it have projective arithmetic. See dalek-cryptography/curve25519-dalek#746.

It should be added then! As it stands without more arithmetic support for the Montgomery curve you can't implement hash_to_curve() (AFAIK).