[GitHub] [incubator-milagro-crypto-rust] mratsim commented on issue #37: Subgroup Checks BLS12-381

[GitBox <gi...@apache.org>]

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:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@milagro.apache.org
For additional commands, e-mail: issues-help@milagro.apache.org