Subgroup membership test for curves which cofactor =/= 1

clearmatics / libff

C++ library for Finite Fields and Elliptic Curves (forked from scipr-lab/libff)

https://clearmatics.github.io/libff/

Other

3 stars 2 forks source link

Subgroup membership test for curves which cofactor =/= 1 #16

Open AntoineRondelet opened 4 years ago

AntoineRondelet commented 4 years ago

For now, no "multiplication by the cofactor" is done in the BLS12_377 implementation. However, the cofactor isn't 1:

u = 0x8508c00000000001

def g1_h(x):
    return ((x-1)**2) // 3

g1_h(u)
# 30631250834960419227450344600217059328

This is obviously insecure and vulnerable to attacks such as the small subgroup attack. Add multiplication by cofactor or subgroup membership test where relevant - i.e. in the deserialization functions etc - (same applies in G2 and for other curves with cofactor =/= 1)

AntoineRondelet commented 4 years ago

If I haven't missed anything, the edward curve implemented in libff doesn't seem to implement Decaf, and has a cofactor = 4. It may be worth double checking as I believe that the subgroup membership tests may have been forgotten. To double check.

AntoineRondelet commented 4 years ago

AntoineRondelet commented 3 years ago

See also, this recent note by M. Scott: https://eprint.iacr.org/2021/1130.pdf