Quadratic and Cubic non-residues for tower of extension fields

mratsim commented 4 years ago

To construct a tower of extension fields we need to find an irreducible polynomial, i.e. For quadratic extension fields:

x² ≢1 (mod p), i.e. x is not a square (mod p)

For cubic extension fields:

x³ ≢1 (mod p), i.e. x is not a cube (mod p)

Unfortunately while for 𝔽p2 most (all?) pairing friendly primes admit the imaginary number 𝑖 as a quadratic non-residue (they are chosen so that the prime p ≡ 3 (mod 4)), the irreducible polynomial for further extensions is likely dependent on the prime chosen.

For example the IETF draft on pairing curves suggests in section 4.3 the following towers:

BN462
- F_p^2 = F_p[u] / (u^2 + 1)
- F_p^6 = F_p^2[v] / (v^3 - u - 2)
- F_p^12 = F_p^6[w] / (w^2 - v).
BLS12-381
- F_p^2 = F_p[u] / (u^2 + 1)
- F_p^6 = F_p^2[v] / (v^3 - u - 1)
- F_p^12 = F_p^6[w] / (w^2 - v).

Given the wide range of curves we need to:

Automatically check at least or find non-residues
Associate the multiplication by non-residue to the curve so that fields like 𝔽p6 can be generically implemented.

Checking or finding non-residues

This was started in Sage at https://github.com/mratsim/constantine/blob/c40bc1977d00dbd87f328a3e410d63b9d85ae458/sage/non_residues.sage

Unfortunately Sage is completely outside my expertise, help wanted, I cannot seem to use the imaginary number 𝑖 to define an extension based on a complex polynomial.

Abstracting over the non-residues

This was somewhat started with this Xi abstract object: https://github.com/mratsim/constantine/blob/c40bc1977d00dbd87f328a3e410d63b9d85ae458/constantine/tower_field_extensions/fp6_1_plus_i.nim#L46-L63

Used like this:

https://github.com/mratsim/constantine/blob/c40bc1977d00dbd87f328a3e410d63b9d85ae458/constantine/tower_field_extensions/fp6_1_plus_i.nim#L153-L168

The way forward is probably to add a config_tower.nim file that would do something like this, Using Xi as the generic name for non-residues

 func `*`(_: typedesc[Xi], a: Fp6[BN254]): Fp6[BN254] {.inline.}=
   discard

 template `*`(a: Fp2, _: typedesc[Xi]): Fp2 = 
   Xi * a 

 func `*=`(a: var Fp6[BN254], _: typedesc[Xi]) {.inline.}= 
   discard

 func `*`(_: typedesc[Xi], a: Fp12[BN254]): Fp12[BN254] {.inline.}=
   when a is CubicExtensionField:
     discard "Implementation for 𝔽p12 = 𝔽p4[w]
  else:
    discard "Implementation for 𝔽p12 = 𝔽p6[w]

 template `*`(a: Fp12, _: typedesc[Xi]): Fp2 = 
   Xi * a 

 func `*=`(a: var Fp12[BN254], _: typedesc[Xi]) {.inline.}= 
   when a is CubicExtensionField:
     discard "Implementation for 𝔽p12 = 𝔽p4[w]
  else:
    discard "Implementation for 𝔽p12 = 𝔽p6[w]

# --------------------------------------------------------------------

 func `*`(_: typedesc[Xi], a: Fp6[BLS12_381]): Fp6[BN256] {.inline.}=
   discard

 template `*`(a: Fp2, _: typedesc[Xi]): Fp2 = 
   Xi * a 

 func `*=`(a: var Fp6[BLS12_381], _: typedesc[Xi]) {.inline.}= 
   discard

 func `*`(_: typedesc[Xi], a: Fp12[BLS12_381]): Fp12[BN256] {.inline.}=
   when a is CubicExtensionField:
     discard "Implementation for 𝔽p12 = 𝔽p4[w]
  else:
    discard "Implementation for 𝔽p12 = 𝔽p6[w]

 template `*`(a: Fp12, _: typedesc[Xi]): Fp2 = 
   Xi * a 

 func `*=`(a: var Fp12[BLS12_381], _: typedesc[Xi]) {.inline.}= 
   when a is CubicExtensionField:
     discard "Implementation for 𝔽p12 = 𝔽p4[w]
  else:
    discard "Implementation for 𝔽p12 = 𝔽p6[w]

This would reuse the Cubic/Quadratic concepts defined in abelian_groups.nim https://github.com/mratsim/constantine/blob/c40bc1977d00dbd87f328a3e410d63b9d85ae458/constantine/tower_field_extensions/abelian_groups.nim#L38-L44 https://github.com/mratsim/constantine/blob/c40bc1977d00dbd87f328a3e410d63b9d85ae458/constantine/tower_field_extensions/abelian_groups.nim#L121-L127

mratsim commented 4 years ago

So literature is contradicting itself (?)

For BN254:

0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47 ≡ 7 (mod 8)

Aranha in https://caramba.loria.fr/sem-slides/201905241000.pdf / https://ecc2017.cs.ru.nl/slides/ecc2017-aranha.pdf mentions that they can use the following towering:

𝔽p²=𝔽p[𝑖]/(i² − β), where β=−1
𝔽p6=𝔽p[v]/(v² − ξ), where ξ=𝑖+1

and https://eprint.iacr.org/2010/526.pdf

But Grewal in https://eprint.iacr.org/2012/408.pdf mentions that for BN curve with p ≡ 7 (mod 8) you need 𝔽p² = √-2

[8] refers to Pereira paper: https://eprint.iacr.org/2010/429.pdf

Edit: From Pereira paper

From Bos, Costello Naehrig https://www.microsoft.com/en-us/research/wp-content/uploads/2013/08/exponentiating_pairing.pdf

mratsim commented 4 years ago

So in Ethereum the curve equation is y^2 = x^3 + 3

But in the papers cited they create y² = x³ + 2. According to Pereira paper, b = N(ξ) (norm of Xi) with ξ = c² + d³ 𝑖, due to b = 2 this works for ξ = 1+𝑖 and bypasses (?) the cubic non-residue requirement. However for Ethereum usage, the curve is y² = x³ + 3 so we can't find "friendly" parameters for y² = x³ + 2 and we need to fallback to cubic non-residue to extend 𝔽p6=𝔽p[v]/(v² − ξ), possible using √-2 instead of 𝑖 for the base quadratic extension.

Can someone with a good grasp on that confirm?

mratsim commented 4 years ago

Confusion solved Snarks and Ethereum use the prime 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47 and Nogami/Aranha and the litterature use 0x2523648240000001ba344d80000000086121000000000013a700000000000013. Both are BN primes of width 254-bit .

The sage formulas have been updated and the suggested towers matches the litterature and specifications.

mratsim / constantine

Quadratic and Cubic non-residues for tower of extension fields #19

Checking or finding non-residues

Abstracting over the non-residues