Subgroup Checks BLS12-381

[kirk-baird]

What is the issue

Subgroup checks are currently being performed using GLV method for G1 and GS method for G2.

This may perform incorrect scalar multiplications for points not in the subgroup, thus a potential for false positives in the subgroup check.

ToDo

Replace subgroup checks with a more accurate and efficient method.

[jon-chuang]

Hi, we are utilising batch subgroup checks that involve adding to random buckets and repeating to exponentially decrease a bounded error. Stay tuned at Zexe for writeup.

[mratsim]

See my comment status-im/nimbus-eth2#1715 (comment)

And the "spec-like" notation at 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