search

zkcrypto / pairing

Pairing-friendly elliptic curve library.
Other
341 stars 120 forks source link

Implement Scott's method for fast cofactor multiplication. #102

Closed mmaker closed 5 years ago

mmaker commented 5 years ago

I've recently been looking at faster way for multiplying by the cofactor over G2. It seems to me that this problem is generally solved in the literature by writing the cofactor (or a multiple of it) modulo q, and using an endomorphism to speed up the computation for scalar multiplication modulo q.

There's two viable methods for BLS12-381: one from Scott et al., one from Budroni et al.. Together with @AnitaDurr we took a chance at implementing Scott's method. There are some trivial optimizations that can still be put in place, but the bottom line is that we can multiply by the cofactor over G2 with 3 scalar multiplications (< r) and 2 point additions.

It seems that relic has also done something similar, however they keep the constant x around and use Alessandro's method, making this slightly slower.

mmaker commented 5 years ago

Hello @daira! Sorry for the very late reply on this pull request. Following the big refactoring that I see on https://github.com/zkcrypto/bls12_381, I'm moving my pull request there, integrating with your comments! It's https://github.com/zkcrypto/bls12_381/pull/18

Thanks for this preliminary review.