Subgroup check

[mratsim]

When verifying signatures we need to discard invalid signatures. In particular, for curves with a cofactor != 1 we need to prevent "subgroup attacks" for which a signature is forged to be on the curve but not in the desired subgroup (see cofactor #46).

Preventing subgroups attacks requires a subgroup check which is a costly scalar multiplication when implemented naively.

This paper from Zcash details a faster alternative:

• Faster Subgroup Checks for BLS12-381
  Sean Bowe, 2019
  https://eprint.iacr.org/2019/814

Pseudo code for BLS12-381: pairingwg/bls_standard#21

Sean Bowe shows how to check subgroup membership more quickly than exponentiation by the group order.

This post quickly summarizes the results as pseudocode.

TODO: should subgroup testing be a required part of deserialization? Sean points out (in personal communication) that G2 subgroup checks are necessary, because the pairing operation is undefined otherwise. So probably it makes sense to just require subgroup checks for both G1 and G2.

For G1, define the endomorphism sigma as

sigma(x, y)

Input: a point P = (x, y)
Output: a point Q = (x', y')

Constants:
1. beta = 0x1a0111ea397fe699ec02408663d4de85aa0d857d89759ad4897d29650fb85f9b409427eb4f49fffd8bfd00000000aaac

Steps:
1. x' = x * beta
2. y' = y
2. return (x', y')

Then, to check subgroup membership, test the following:

subgroup_test_g1(x, y)

Input: a point P
Output: True if P is in the order-q subgroup of E1, else False

Constants:
- c1 = (z^2 - 1) / 3 (in the integers), where z = -0xd201000000010000
- point_at_infinity_E1 is the point at infinity on E1

Steps:
1. sP = sigma(P)
2. Q = 2 * sP
3. sP = sigma(sP)
4. Q = Q - P
5. Q = Q - sP
6. Q = c1 * Q
7. Q = Q - sP
8. return Q == point_at_infinity_E1

For G2, let psi(P) be the "untwist-Frobenius-twist" endomorphism given by Galbraith and Scott in Section 5 of GS08. Then to test subgroup membership, check the following:

subgroup_test_g2(P)

Input: a point P
Output: True if P is in the order-q subgroup of E2, else False

Constants:
- z = -0xd201000000010000
- point_at_infinity_E2 is the point at infinity on E2

Steps:
1. pP = psi(P)
2. pP = psi(pP)
3. Q = P - pP
4. pP = psi(pP)
5. pP = z * pP
6. Q = Q + pP
7. return Q == point_at_infinity_E2

[paulmillr]

Note that instead of using endomorphism sigma, for G1 it's faster to simply multiply-unsafely by h_eff which is 0xd201000000010001. At least from my tests.

[paulmillr]

I take it back. These x, y produce point which is valid if you multiply it by h_eff, but are invalid if you apply endomorphism sigma.

x=499001545268060011619089734015590154568173930614466321429631711131511181286230338880376679848890024401335766847607;
y=3934582309586258715640230772291917282844636728991757779640464479794033391537662970190753981664259511166946374555673;

[mratsim]

Faster subgroup check: https://eprint.iacr.org/2021/1130.pdf