Efficiently computing tower fields for pairings

Anonymous

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?

Comments

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 ( 5 years ago )

@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 use w on the RHS of that expression (nor can I use v, 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 in F6or K6 and associated terms. Have edited my question with what I think is the correct derivation based on your comment.

zahllos ( 5 years ago )

By my comment I meant that after defining F2 with generator u, you can do (instead of your code):

R.<y> = PolynomialRing(F2)
F12.<w> = F2.extension(y^6 - (u+1))
v = w^2

rburing ( 5 years ago )

add a comment

answered 5 years ago

dan_fulea
5650 ●5 ●44 ●97

We can start with a default version of $F=\Bbb F_q$ , $q=p^{12}$ , construct $w$ inside it, ask for the minimal polynomial $P$ of $w$ , and work further with $F$ . Or construct $K\cong F$ by using $K=\Bbb F_p[X]/(P)$ . Let us construct $w$ in the "default" world.

F = GF(0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab)
p = F.characteristic()
F12.<G> = GF(p^12)    # G is the generator, we will not need it below

u = sqrt(F12(-1))
R12.<Y> = PolynomialRing(F12)

v = (Y^3 - (u+1)).roots(multiplicities=False)[0]
w = sqrt(v)

P = w.minpoly()

As expected, we get a polynomial P of degree $12$ , and now we may want to switch to

K.<W> = GF(p^12, modulus=P)

Here,

sage: P                                                                                                                              
x^12 + 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559785*x^6 + 2
sage:

link

add a comment

Efficiently computing tower fields for pairings

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

Efficiently computing tower fields for pairings savecancel

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

Efficiently computing tower fields for pairings