ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 31 Jan 2020 12:46:06 +0100Efficiently computing tower fields for pairingshttps://ask.sagemath.org/question/49663/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?Fri, 24 Jan 2020 02:02:27 +0100https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/Comment by rburing for <p>Hello all,</p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>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). </p>
<p>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). </p>
<p>Taking the cue from faster subgroup checks for bls12, I tried to redefine this as:</p>
<pre><code>F12.<w> = F6.extension(x^2 - v)
</code></pre>
<p>but this fails with a type conversion error.</p>
<p>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?</p>
<p>Apologies for the broken links, I'm not allowed to include links yet.</p>
<hr>
<p><strong>Update</strong>: Following <a href="/users/24971/rburing/">@rburing</a>'s comment, I noted that the tower field is as follows:</p>
<p>$$\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) $$</p>
<p>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:</p>
<p>$$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^2}[a]/((a+1)-(a+1)^3)$$</p>
<p>which can be represented two ways in sage:</p>
<pre><code>F12.<w> = F2.extension((u+1)-(x^2+2)^3)
F12a.<q> = F2.extension((u+1)-(u+1)^3)
</code></pre>
<p>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:</p>
<pre><code>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
</code></pre>
<p>My question is, is this the correct object?</p>
https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?comment=49666#post-id-49666Note $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$.Fri, 24 Jan 2020 13:11:42 +0100https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?comment=49666#post-id-49666Comment by zahllos for <p>Hello all,</p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>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). </p>
<p>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). </p>
<p>Taking the cue from faster subgroup checks for bls12, I tried to redefine this as:</p>
<pre><code>F12.<w> = F6.extension(x^2 - v)
</code></pre>
<p>but this fails with a type conversion error.</p>
<p>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?</p>
<p>Apologies for the broken links, I'm not allowed to include links yet.</p>
<hr>
<p><strong>Update</strong>: Following <a href="/users/24971/rburing/">@rburing</a>'s comment, I noted that the tower field is as follows:</p>
<p>$$\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) $$</p>
<p>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:</p>
<p>$$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^2}[a]/((a+1)-(a+1)^3)$$</p>
<p>which can be represented two ways in sage:</p>
<pre><code>F12.<w> = F2.extension((u+1)-(x^2+2)^3)
F12a.<q> = F2.extension((u+1)-(u+1)^3)
</code></pre>
<p>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:</p>
<pre><code>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
</code></pre>
<p>My question is, is this the correct object?</p>
https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?comment=49668#post-id-49668@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 `F6`or `K6` and associated terms. Have edited my question with what I think is the correct derivation based on your comment.Fri, 24 Jan 2020 17:55:26 +0100https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?comment=49668#post-id-49668Comment by rburing for <p>Hello all,</p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>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). </p>
<p>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). </p>
<p>Taking the cue from faster subgroup checks for bls12, I tried to redefine this as:</p>
<pre><code>F12.<w> = F6.extension(x^2 - v)
</code></pre>
<p>but this fails with a type conversion error.</p>
<p>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?</p>
<p>Apologies for the broken links, I'm not allowed to include links yet.</p>
<hr>
<p><strong>Update</strong>: Following <a href="/users/24971/rburing/">@rburing</a>'s comment, I noted that the tower field is as follows:</p>
<p>$$\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) $$</p>
<p>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:</p>
<p>$$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^2}[a]/((a+1)-(a+1)^3)$$</p>
<p>which can be represented two ways in sage:</p>
<pre><code>F12.<w> = F2.extension((u+1)-(x^2+2)^3)
F12a.<q> = F2.extension((u+1)-(u+1)^3)
</code></pre>
<p>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:</p>
<pre><code>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
</code></pre>
<p>My question is, is this the correct object?</p>
https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?comment=49672#post-id-49672By 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^2Fri, 24 Jan 2020 21:23:59 +0100https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?comment=49672#post-id-49672Answer by dan_fulea for <p>Hello all,</p>
<p>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:</p>
<pre><code>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)
</code></pre>
<p>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). </p>
<p>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). </p>
<p>Taking the cue from faster subgroup checks for bls12, I tried to redefine this as:</p>
<pre><code>F12.<w> = F6.extension(x^2 - v)
</code></pre>
<p>but this fails with a type conversion error.</p>
<p>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?</p>
<p>Apologies for the broken links, I'm not allowed to include links yet.</p>
<hr>
<p><strong>Update</strong>: Following <a href="/users/24971/rburing/">@rburing</a>'s comment, I noted that the tower field is as follows:</p>
<p>$$\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) $$</p>
<p>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:</p>
<p>$$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^2}[a]/((a+1)-(a+1)^3)$$</p>
<p>which can be represented two ways in sage:</p>
<pre><code>F12.<w> = F2.extension((u+1)-(x^2+2)^3)
F12a.<q> = F2.extension((u+1)-(u+1)^3)
</code></pre>
<p>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:</p>
<pre><code>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
</code></pre>
<p>My question is, is this the correct object?</p>
https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?answer=49726#post-id-49726We 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: Fri, 31 Jan 2020 12:46:06 +0100https://ask.sagemath.org/question/49663/efficiently-computing-tower-fields-for-pairings/?answer=49726#post-id-49726