Implement BW6-761 curve

[yelhousni]

152.

This PR implements BW6-761 curve from [HG20]. Type: Enhancement Label: Ready to review Priority: Medium

Motivation

Substitute the outer curve SW6 curve by the much faster curve BW6-761.

Description

This PR implements the fields and groups instantiation of the curve (and its twist) and an optimal ate pairing in [ABLR13] projective coordinates with a sextic M-twist (G2 over Fq, 2 small Miller loops (Alg.5) and a lattice-based optimized final exp (Alg.6)).

Followups:

There are few optimizations to do further:

• [x] use 2-NAF in the Miller loop
• [ ] instantiate the second Miller loop by the first (optimization described in Alg.5)
• [ ] hash-to-curve (Elligator-2 for G1 and a SW variant for G2)
• [ ] use of endomorphism (GLV multiplication, cofactor clearing and subgroup checks over G1 and G2)

[Pratyush]

Thanks for the awesome PR @yelhousni! Quick question: I see that the BW6Engine and BW6Parameters are defined in algebra-core and not in algebra. Is this because it works for any curve in the BW6 family?

[yelhousni]

@Pratyush LGTM, suggested changes are applied. BW6Engine is in algebra-core because indeed it works for any Brezing-Weng family of embedding degree k=6. As an example, the branches youssef/BW6-761-Fq-*-*-D use a D-twist with different curve parameters.

[yelhousni]

Actually, the 2-NAF method is only faster for the second ML because the hamming weight of the first ML in binary is the same as in 2-NAF. With this additional optimization, we reach a speedup of 32X for a Miller loop compared to SW6 and thus ~23.5X for a Groth16 proof verification.

[Pratyush]

@yelhousni this looks great to me! do you want to merge now, or do you want to implement the other optimizations that you mentiond above?

[yelhousni]

@Pratyush Let's merge now and later we can add the other optimizations.

[Pratyush]

Great!