elliptic-curve: hash-to-curve support

[kevinlewi]

It would be nice to have support for a from_uniform_bytes functionality for the elliptic curve implementations that performs the hash-to-curve operations described here, preferably the _SSWU_RO_ variants!

[burdges]

I'd expect some churn coming based upon https://mailarchive.ietf.org/arch/msg/cfrg/ZYlKNd4JJiJxNTYSwrY-ZFb4LeI/

[tarcieri]

I think we can potentially work on some hash-to-curve traits while the spec is still in flux.

Note that there is a FromDigest trait, however I have some misgivings about it: it's presently used for hash-to-scalar for the purposes of ECDSA, and as much, I've thought about moving it to the ecdsa crate for the next release. Edit: removed in elliptic-curve v0.9, clearing the way for new hash-to-curve traits

[tarcieri]

Here's a library that implements draft-irtf-cfrg-hash-to-curve-11 and provides some traits: https://crates.io/crates/hash2field

It provides an example for using it with k256.

cc @mikelodder7

[mikelodder7]

I'm also working on crates for the optimized swu map and isogeny map if that helps. The idea is I've implemented hash2curve so many times and in no-std settings that the spec hasn't changed much in terms of code over time. Mostly just updating the information.

[newpavlov]

Continuation of this discussion: RustCrypto/elliptic-curves#432 (comment)

But I don't get how that works

D::OutputSize: IsEqual<U32> + IsEqual<U64> effectively says "OutputSize can be compared against U32 and U64", i.e. it's a constrain on "capability" which this type posses, not equality check itself. Same goes for Eq<D::OutputSize, U32>: BitOr<Eq<D::OutputSize, U64>>, it means "we can apply OR to the equality check results".

typenum is somewhat counter-intuitive, since you have to explicitly state a lot of "obvious" stuff.

I need to bound on support for a specific digest size

I am not sure I see a problem (though I can't say I 100% understand your snippet). SigningKey is based on Scalar, correct? So bounds of the latter will inevitably leak to bounds of the former. Can you explain what constraints you would like to express?

[tarcieri]

Looking at this gist again:

https://play.rust-lang.org/?gist=6547bf4c636d51196326fd26aa4bbdee

...it seems pretty problematic that the scalar type is parameterized by a Digest. Scalars have nothing to do with digests, or rather, the relationship is at most a From one. In fact the elliptic-curve crate does not presently depend on the digest crate at all.

I am not sure I see a problem (though I can't say I 100% understand your snippet). SigningKey is based on Scalar, correct? So bounds of the latter will inevitably leak to bounds of the former. Can you explain what constraints you would like to express?

The main bound I need for ECDSA is this one:

Scalar<C>: FromDigest<FieldSize<C>>

I want to express that a particular scalar type impls FromDigest with a digest output size equal to the size of the curve's scalar field. Right now that's a hardcoded assumption in ecdsa::FromDigest, but in a more general one it should be possible to support conversions from multiple digest sizes, and for ECDSA to be able to select the correct one.

[newpavlov]

...it seems pretty problematic that the scalar type is parameterized by a Digest. Scalars have nothing to do with digests, or rather, the relationship is at most a From one.

This is why I wrote that this trait probably should be implemented by a wrapper. I do agree that it's worth to keep elliptic-curve and implementation crates hash-agnostic. It looks a bit strange to bother to the level of passing unfinalized hash function instead of hash value and loose the type-level tracking of used hash function immediately afterwards.

I want to express that a particular scalar type impls FromDigest with a digest output size equal to the size of the curve's scalar field.

Then write this constraint directly as I've done it in the snippet using the typenum operators and marker traits?

[tarcieri]

I don't understand how to express that, and as a general comment I find those trait bounds extremely hard to read.

[tarcieri]

It looks a bit strange to bother to the level of passing unfinalized hash function instead of hash value and loose the type-level tracking of used hash function immediately afterwards.

The primary rationale for that is a misuse-resistant API which upholds the requirements of e.g. the Fiat-Shamir heuristic. See:

• https://docs.rs/signature/1.3.1/signature/trait.DigestSigner.html#notes
• https://docs.rs/signature/1.3.1/signature/trait.DigestVerifier.html#notes

[tarcieri]

I would consider the hash-to-scalar case mostly addressed by the introduction of a Reduce trait in #768. We could perhaps add direct support for computing a Scalar from a Digest, but otherwise it's a simple composition of the Reduce+Digest traits.

The larger remaining issue is hashing to elliptic curve points ala draft-irtf-cfrg-hash-to-curve. We need to define traits, and then implement those traits in the k256/p256 crates.

Perhaps we could look to something like @mikelodder7's aforementioned hash2curve crate for inspiration.

[str4d]

The bls12_381 crate has an implementation of the hash-to-curve ID that is both no-std compatible and uses HashToField and HashToCurve traits: https://github.com/zkcrypto/bls12_381/blob/main/src/hash_to_curve/mod.rs

The impl is currently behind an experimental feature flag, both in case the ID changes, and because we wanted feedback on the trait design. I'd be happy to help uplift (something like) those traits into either group or elliptic-curve.

[daxpedda]

Just linking the current progress so people can chime in on their needs:

• feat: add osswu trait #854
• feat: add hash to field #855
• feat: add traits for group digest #865
• ExpandMsg improvements #874
• Improve API for hash2curve functions #876

And the actual implementation on curves:

• feat: hash to curve elliptic-curves#495 (outdated)
• Implement GroupDigest for NistP256 and Secp256k1 elliptic-curves#503

[daxpedda]

I guess this can be closed now? Just waiting for a new release.

[tarcieri]

I can cut a release, but please keep in mind that once I do all features are stable until the next breaking release.

Are you ready for that? Alternatively we can try to land the PRs to https://github.com/RustCrypto/elliptic-curves first (using a [patch.crates-io] directive to pull in elliptic-curve via git)

[daxpedda]

I didn't actually mean to ask for a release, but it would actually be great. I already tried the API for the projects I'm working on, so as far as I'm concerned the API is fine. I noticed a small thing that could be improved that I will PR for.

Alternatively we can try to land the PRs to https://github.com/RustCrypto/elliptic-curves first (using a [patch.crates-io] directive to pull in elliptic-curve via git)

Why? What do you have in mind we would gain from doing that first?

[tarcieri]

If you're happy with the API, then I can go ahead and cut a release.

@mikelodder7 are you ok with that?

[daxpedda]

See #881. Otherwise I'm good to go.

[mikelodder7]

Yes I’m happy with where we’ve landed

[tarcieri]

I think we're good to go here now