mratsim commented on issue #37: URL: https://github.com/apache/incubator-milagro-crypto-rust/issues/37#issuecomment-696739320
See my comment https://github.com/status-im/nim-beacon-chain/issues/1715#issuecomment-696595037 And the "spec-like" notation at https://github.com/pairingwg/bls_standard/issues/21 > Sean Bowe [shows](https://eprint.iacr.org/2019/814) 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](https://eprint.iacr.org/2008/117). 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 > ``` ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@milagro.apache.org For additional commands, e-mail: issues-h...@milagro.apache.org
