bls12_377_subgroups.nim
1 # Constantine 2 # Copyright (c) 2018-2019 Status Research & Development GmbH 3 # Copyright (c) 2020-Present Mamy André-Ratsimbazafy 4 # Licensed and distributed under either of 5 # * MIT license (license terms in the root directory or at http://opensource.org/licenses/MIT). 6 # * Apache v2 license (license terms in the root directory or at http://www.apache.org/licenses/LICENSE-2.0). 7 # at your option. This file may not be copied, modified, or distributed except according to those terms. 8 9 import 10 # Internals 11 ../../platforms/abstractions, 12 ../config/curves, 13 ../arithmetic, 14 ../extension_fields, 15 ../ec_shortweierstrass, 16 ../io/io_bigints, 17 ../isogenies/frobenius, 18 ../constants/zoo_endomorphisms 19 20 func pow_bls12_377_abs_x[ECP: ECP_ShortW[Fp[BLS12_377], G1] or 21 ECP_ShortW[Fp2[BLS12_377], G2]]( 22 r{.noalias.}: var ECP, 23 P{.noalias.}: ECP 24 ) = 25 ## Does the scalar multiplication [x]P 26 ## with x the absolute value of the BLS12 curve parameter 27 ## For BLS12_377 [0x8508c00000000001]P 28 ## Requires r and P to not alias 29 r.double(P) 30 r += P 31 r.double() 32 r += P 33 let t111 = r 34 35 r.double_repeated(2) 36 let t111000 = r 37 38 r += t111 39 let t100011 = r 40 41 r.double() 42 r += t100011 43 r += t111000 44 45 r.double_repeated(10) 46 r += t100011 47 48 r.double_repeated(46) 49 r += P 50 51 func pow_bls12_377_x[ECP: ECP_ShortW[Fp[BLS12_377], G1] or 52 ECP_ShortW[Fp2[BLS12_377], G2]]( 53 r{.noalias.}: var ECP, 54 P{.noalias.}: ECP 55 ) {.inline.}= 56 ## Does the scalar multiplication [x]P 57 ## with x the BLS12 curve parameter 58 ## For BLS12_377 [0x8508c00000000001]P 59 ## Requires r and P to not alias 60 pow_bls12_377_abs_x(r, P) 61 62 func pow_bls12_377_minus_x[ECP: ECP_ShortW[Fp[BLS12_377], G1] or 63 ECP_ShortW[Fp2[BLS12_377], G2]]( 64 r{.noalias.}: var ECP, 65 P{.noalias.}: ECP 66 ) {.inline.}= 67 ## Does the scalar multiplication [-x]P 68 ## with x the BLS12 curve parameter 69 ## For BLS12_377 [-0x8508c00000000001]P 70 ## Requires r and P to not alias 71 pow_bls12_377_abs_x(r, P) 72 r.neg() 73 74 # ############################################################ 75 # 76 # Clear Cofactor - Naive 77 # 78 # ############################################################ 79 80 const Cofactor_Eff_BLS12_377_G1 = BigInt[64].fromHex"0x8508c00000000000" 81 ## P -> (1 - x) P 82 const Cofactor_Eff_BLS12_377_G2 = BigInt[629].fromHex"0x1f60243677e30653648d3d9502abfba951764c46f4edd28f6ade35a5c7d769f7ee7c4b03103b45b85860aaaad2927678ba2796373885598e8e73ad8a538800cf664765b00000031e34800000000000" 83 ## P -> (x^2 - x - 1) P + (x - 1) ψ(P) + ψ(ψ(2P)) 84 ## 85 ## Effective cofactor from Budroni et al https://eprint.iacr.org/2017/419.pdf 86 ## (3x² − 3)*cofactor 87 88 func clearCofactorReference*(P: var ECP_ShortW_Prj[Fp[BLS12_377], G1]) {.inline.} = 89 ## Clear the cofactor of BLS12_377 G1 90 # Endomorphism acceleration cannot be used if cofactor is not cleared 91 P.scalarMulGeneric(Cofactor_Eff_BLS12_377_G1) 92 P.neg() 93 94 func clearCofactorReference*(P: var ECP_ShortW_Prj[Fp2[BLS12_377], G2]) {.inline.} = 95 ## Clear the cofactor of BLS12_377 G2 96 # Endomorphism acceleration cannot be used if cofactor is not cleared 97 P.scalarMulGeneric(Cofactor_Eff_BLS12_377_G2) 98 99 # ############################################################ 100 # 101 # Clear Cofactor - Optimized 102 # 103 # ############################################################ 104 105 # BLS12 G1 106 # ------------------------------------------------------------ 107 108 func clearCofactorFast*(P: var ECP_ShortW[Fp[BLS12_377], G1]) = 109 ## Clear the cofactor of BLS12_377 G1 110 ## 111 ## Wahby et al "Fast and simple constant-time hashing to the BLS12-377 elliptic curve", https://eprint.iacr.org/2019/403 112 ## Optimized using endomorphisms 113 ## P -> (1 - x) P 114 var t{.noInit.}: typeof(P) 115 t.pow_bls12_377_minus_x(P) # [-x]P 116 P += t # [1-x]P 117 118 # BLS12 G2 119 # ------------------------------------------------------------ 120 # From any point on the elliptic curve E2 of a BLS12 curve 121 # Obtain a point in the G2 prime-order subgroup 122 # 123 # Described in https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#appendix-G.4 124 # 125 # Implementations, multiple implementations are possible in increasing order of speed: 126 # 127 # - The default, canonical, implementation is h_eff * P 128 # - Scott et al, "Fast Hashing to G2 on Pairing-Friendly Curves", https://doi.org/10.1007/978-3-642-03298-1_8 129 # - Fuentes-Castaneda et al, "Fast Hashing to G2 on Pairing-Friendly Curves", https://doi.org/10.1007/978-3-642-28496-0_25 130 # - Budroni et al, "Hashing to G2 on BLS pairing-friendly curves", https://doi.org/10.1145/3313880.3313884 131 # - Wahby et al "Fast and simple constant-time hashing to the BLS12-377 elliptic curve", https://eprint.iacr.org/2019/403 132 # - IETF "Hashing to Elliptic Curves", https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#appendix-G.4 133 # 134 # In summary, the elliptic curve point multiplication is very expensive, 135 # the fast methods uses endomorphism acceleration instead. 136 # 137 # The method described in Wahby et al is implemented by Riad Wahby 138 # in C at: https://github.com/kwantam/bls12-377_hash/blob/23c1930039f58606138459557677668fabc8ce39/src/curve2/ops2.c#L106-L204 139 # following Budroni et al, "Efficient hash maps to G2 on BLS curves" 140 # https://eprint.iacr.org/2017/419 141 # 142 # "P -> [x² - x - 1] P + [x - 1] ψ(P) + ψ(ψ([2]P))" 143 # 144 # with Psi (ψ) - untwist-Frobenius-Twist function 145 # and x the curve BLS parameter 146 147 func clearCofactorFast*(P: var ECP_ShortW[Fp2[BLS12_377], G2]) = 148 ## Clear the cofactor of BLS12_377 G2 149 ## Optimized using endomorphisms 150 ## P -> [x²-x-1]P + [x-1] ψ(P) + ψ²([2]P) 151 152 var xP{.noInit.}, x2P{.noInit.}: typeof(P) 153 154 xP.pow_bls12_377_x(P) # 1. xP = [x]P 155 x2P.pow_bls12_377_x(xP) # 2. x2P = [x²]P 156 157 x2P.diff(x2P, xP) # 3. x2P = [x²-x]P 158 x2P.diff(x2P, P) # 4. x2P = [x²-x-1]P 159 160 xP.diff(xP, P) # 5. xP = [x-1]P 161 xP.frobenius_psi(xP) # 6. xP = ψ([x-1]P) = [x-1] ψ(P) 162 163 P.double(P) # 7. P = [2]P 164 P.frobenius_psi(P, k=2) # 8. P = ψ²([2]P) 165 166 P.sum(P, x2P) # 9. P = [x²-x-1]P + ψ²([2]P) 167 P.sum(P, xP) # 10. P = [x²-x-1]P + [x-1] ψ(P) + ψ²([2]P) 168 169 # ############################################################ 170 # 171 # Subgroup checks 172 # 173 # ############################################################ 174 175 func isInSubgroup*(P: ECP_ShortW[Fp[BLS12_377], G1]): SecretBool = 176 ## Returns true if P is in G1 subgroup, i.e. P is a point of order r. 177 ## A point may be on a curve but not on the prime order r subgroup. 178 ## Not checking subgroup exposes a protocol to small subgroup attacks. 179 ## 180 ## Warning ⚠: Assumes that P is on curve 181 # Implementation: Scott, https://eprint.iacr.org/2021/1130.pdf 182 # A note on group membership tests for G1, G2 and GT 183 # on BLS pairing-friendly curves 184 # P is in the G1 subgroup iff ϕ(P) == [-u²](P) 185 var t0{.noInit.}, t1{.noInit.}: typeof(P) 186 187 # [-u²]P 188 t0.pow_bls12_377_x(P) 189 t1.pow_bls12_377_minus_x(t0) 190 191 # ϕ(P) 192 t0.x.prod(P.x, BLS12_377.getCubicRootOfUnity_mod_p()) 193 t0.y = P.y 194 t0.z = P.z 195 196 return t0 == t1 197 198 func isInSubgroup*(P: ECP_ShortW[Fp2[BLS12_377], G2]): SecretBool = 199 ## Returns true if P is in G2 subgroup, i.e. P is a point of order r. 200 ## A point may be on a curve but not on the prime order r subgroup. 201 ## Not checking subgroup exposes a protocol to small subgroup attacks. 202 ## 203 ## Warning ⚠: Assumes that P is on curve 204 # Implementation: Scott, https://eprint.iacr.org/2021/1130.pdf 205 # A note on group membership tests for G1, G2 and GT 206 # on BLS pairing-friendly curves 207 # P is in the G1 subgroup iff ψ(P) == [u](P) 208 var t0{.noInit.}, t1{.noInit.}: typeof(P) 209 t0.pow_bls12_377_x(P) # [u]P 210 t1.frobenius_psi(P) # ψ(P) 211 212 return t0 == t1 213 214 func isInSubgroup*(P: ECP_ShortW_Aff[Fp[BLS12_377], G1]): SecretBool = 215 ## Returns true if P is in 𝔾1 subgroup, i.e. P is a point of order r. 216 ## A point may be on a curve but not on the prime order r subgroup. 217 ## Not checking subgroup exposes a protocol to small subgroup attacks. 218 ## 219 ## Warning ⚠: Assumes that P is on curve 220 var t{.noInit.}: ECP_ShortW_Prj[Fp[BLS12_377], G1] 221 t.fromAffine(P) 222 return t.isInSubgroup() 223 224 225 func isInSubgroup*(P: ECP_ShortW_Aff[Fp2[BLS12_377], G2]): SecretBool = 226 ## Returns true if P is in 𝔾2 subgroup, i.e. P is a point of order r. 227 ## A point may be on a curve but not on the prime order r subgroup. 228 ## Not checking subgroup exposes a protocol to small subgroup attacks. 229 ## 230 ## Warning ⚠: Assumes that P is on curve 231 var t{.noInit.}: ECP_ShortW_Jac[Fp2[BLS12_377], G2] 232 t.fromAffine(P) 233 return t.isInSubgroup()