search

Consensys / gnark-crypto

gnark-crypto provides elliptic curve and pairing-based cryptography on BN, BLS12, BLS24 and BW6 curves. It also provides various algorithms (algebra, crypto) of particular interest to zero knowledge proof systems.
Apache License 2.0
495 stars 160 forks source link

Faster subgroup checks on G2 on most curves #122

Closed mratsim closed 2 years ago

mratsim commented 2 years ago

I've had a look in the library and it seems like Scott optimization in was implemented only for BLS12-381 (paper: https://eprint.iacr.org/2021/1130.pdf)

It is however applicable for all curves where gcd(h₁, h₂) == 1 with h₁ and h₂ the cofactors on G₁ and G₂. In that case it is enough to check that ψ(P) = [t-1]P with t the trace.

As h₁ = 1 for BN curves and t-1 = 6u², it is applicable to BN254. It is noted in the discussion that it also works for BLS24 curves.

yelhousni commented 2 years ago

Hi @mratsim, I think that the G2 trick is implemented for BLS12-381, BLS12-377 and BN254 (but not BLS24-315 indeed).

mratsim commented 2 years ago

Oh indeed, I have a clone older than https://github.com/ConsenSys/gnark-crypto/pull/95/files

yelhousni commented 2 years ago

So there was an error in Scott preprint for G2 membership test proof. However, the result is still correct (more on that here: https://eprint.iacr.org/2022/352.pdf).