Interest in faster implementation of scalar multiplication in G1/G2

[dfaranha]

Hi,

I have a bunch of optimizations for faster G1/G2 scalar multiplications sitting in a fork at https://github.com/dfaranha/bls12_381

These provide a 2x speedup and include:

• Regular w-NAF recodings to reduce the number of point additions in comparison to double-and-always add
• GLV recoding for scalar decomposition, combined with interleaving to save half of the point doublings
• Moving to homogeneous projective coordinates for pairing computation to unify point arithmetic

Some technical details can be found at https://skillsmatter.com/skillscasts/17052-experimenting-with-faster-elliptic-curves-in-rust

I would like to know if there is interest in merging, so it makes sense to put time on preparing a proper pull request.

Thank you for your attention!

[str4d]

I'm definitely interested!

• We do have w-NAF logic in the group crate (via the group::Wnaf struct) that is used on a targeted basis outside this crate for speeding up specific APIs (e.g. Zcash trial-decryption), but it would be great to use it more uniformly.
• I don't have specific comments on the other two suggestions, other than to say we prefer to use constant-time algorithms wherever possible (so that consumers of the crate have fewer things to worry about), and it sounds like these are compatible with that preference.

[randombit]

@dfaranha Any update on this? We're using this crate for BLS signatures and having faster scalar mult would provide a very nice improvement.

[dfaranha]

Sorry for the wait, my teaching-heavy semester started in early August and I suddenly had to prioritize other stuff.

I prepared a pull request with the supposedly simpler G1 parts here: https://github.com/zkcrypto/bls12_381/pull/79