Efficiently computing tower fields for pairings
Hello all,
I'm messing around trying to create a toy bls12-381 implementation. In order to create the required tower of fields, I'm doing this:
reset()
F = GF(0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab)
g1curve = EllipticCurve(F, [0,4])
K2.<x> = PolynomialRing(F)
F2.<u> = F.extension(x^2+1)
K6.<y> = PolynomialRing(F2)
F6.<v> = F2.extension(y^3 - (u+1))
K12.<z> = PolynomialRing(F6)
F12.<w> = F6.extension(z^2 - v)
Such towering is described in multiple places, e.g, Optimal Ate Pairings at the 128-bit Security level (hxxps://hal.archives-ouvertes.fr/hal-01620848/document), Implementing Pairings at the 192-bit Security Level (hxxps://eprint.iacr.org/2012/232.pdf) and Faster Subgroup Checks for BLS12-381 (hxxps://pdfs.semanticscholar.org/f413/bf4f22f682043616261e463abd0fd9fdcc54.pdf).
I am implementing example code given in Guide to Pairing Based Cryptography (hxxps://www.crcpress.com/Guide-to-Pairing-Based-Cryptography/Mrabet-Joye/p/book/9781498729505) that relies on the w $F_p^{12}$ element defined in the above extension tower. However, the last step, of this code appears to take an inordinate amount of time (yet to see it complete).
Taking the cue from faster subgroup checks for bls12, I tried to redefine this as:
F12.<w> = F6.extension(x^2 - v)
but this fails with a type conversion error.
I've tried to search this site to find out how I might generate F12 directly from F2 as I've seen comments indicating that performance of towers of field extensions is... not great and this is also my experience. I have tried to define Fp12 entirely in terms of x from the first PolynomialRing, but I haven't found a way to try to extend directly from Fp2 to Fp12 yet (I only need Fp12 and its sextic twist. I have seen how to create a homomorphism to embed one elements in another field, but I haven't yet tried to use this to simplify. Can this be done? Is there a way to make this performant?
Apologies for the broken links, I'm not allowed to include links yet.
Update: Following @rburing's comment, I noted that the tower field is as follows:
$$\mathbb{F}_{p^2} = \mathbb{F}_p[a]/(a^2+1) $$ $$\mathbb{F}_{p^6} = \mathbb{F}_{p^2}[b]/(b^3-(a+1)) $$ $$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^{12}}[c]/(c^2-b) $$
From this we have that $b^3 = a+1$ and $c^2 = b$, hence $c$ alone being a sixth root of $a+1$. If $c$ is a sixth root, then $c^2$ is a third root, so $c^2 = (a+1)^(1/3)$ and we can see also that $b=a+1$. To give sage some help, we cube both terms. I think therefore that:
$$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^2}[a]/((a+1)-(a+1)^3)$$
which can be represented two ways in sage:
F12.<w> = F2.extension((u+1)-(x^2+2)^3)
F12a.<q> = F2.extension((u+1)-(u+1)^3)
Sage dislikes the latter ("finite field in u is not alphanumeric") but the former at least constructs and object in a second or two, and gives:
F12
Univariate Quotient Polynomial Ring in w over Finite Field in u of size 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787^2 with modulus w^6 + 6*w^4 + 12*w^2 + 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559786*u + 7
My question is, is this the correct object?
Note $w$ is a sixth root of $u+1$, since $w$ is a square root of $v$ and $v$ is a cube root of $u+1$. So you can define the extension from $\mathbb{F}_{p^2} = \mathbb{F}_p[u]/(u^2+1)$ to $\mathbb{F}_{p^{12}}$ by $\mathbb{F}_{p^{12}} := \mathbb{F}_{p^2}[w]/(w^6 - (u+1))$, and put $v = w^2$.
@rburing Thanks. Unfortunately, this is hard to translate to sage, because $F_p^{12}[w]$ for example is defined by
F12.<w> = ...and I can't usewon the RHS of that expression (nor can I usev, because that's the polynomial ring in the intermediate extension field $F_p^6$ and my hypothesis is that sage just can't cope with this level of towering, so I was hoping simply not to use anything inF6orK6and associated terms. Have edited my question with what I think is the correct derivation based on your comment.By my comment I meant that after defining
F2with generatoru, you can do (instead of your code):