Sextic twist optimization of BN pairing - cubic root extraction required?

Question

I found the following paper really interesting:

http://www.researchgate.net/publication/220378229_A_family_of_implementation-friendly_BN_elliptic_curves/file/79e4150b3a773beecd.pdf

It allows construction of a subset of BN curves where it easy to find the sextic twist. For instance, one knows through the contruction that the sextic twist will be the D-type which means one doesn't have to count points on the elliptic curves to check their order. Also, it gives explicit parameters for the generators of the involved subgroups.

Anyway there's one thing I'm wondering which the paper doesn't go into. Having determined the sextic twist and its generator, how do I map points on the twist back to the "real" curve over $p^{12}$? Other papers specify an isomorphism like:

$(x,y) \to (i^{1/3} x, i^{1/2} y$)

for the D-type (where $i$ plays the role of the epsilon in the paper mentioned). But how do I find the cube-root of $i$? It has to be found when $i$ is interpreted as an element of the finite field of size $p^{12}$ (probably represented using tower polynomials which the paper also describes? I have no problems understanding how to do ordinary arithmetic in this field but I don't know how to do cubic root extraction.

Also, I'm wondering if I'm completely off track because one of the benefits on the construction mentioned in the paper should be that one doesn't have to do cubic root extraction!

Answer 1

You need to recall how the extension is built. $\mathbb{F}_{p^{12}}$ is built on top of $\mathbb{F}_{p^2}$ using the reduction polynomial $f(x) = x^6 - \xi$, where $\xi \in \mathbb{F}_{p^2}$ is a non-square and non-cube (using the notation from the paper). In other words, this is the set of polynomials with coefficients in $\mathbb{F}_{p^2}$, modulo $f(x)$.

Since we're working modulo $f(x)$, then $f(x) = 0$ which means that you can write $x = \sqrt[6]{\xi}$. However, this does not mean that you actually carry out the sextic root (it does not exist in $\mathbb{F}_{p^2}$), but you can "define" the sextic root of $\xi$ as $x$ (which is an element of $\mathbb{F}_{p^{12}}$: $x = 0x^5 + 0x^4 + 0x^3 + 0x^2 + 1x^1 + 0$). This process is called "adjoining roots": here is a good explanation. (A good analogue is with how you build the complex numbers by "defining" $i$ as the square root of $-1$, which does not exist in the reals).

In your question, $i = \xi$. This means that $i^{1/2} = (i^{1/6})^3 = x^3$ and $i^{1/3} = (i^{1/6})^2 = x^2$. They are just $\mathbb{F}_{p^{12}}$ elements with one coefficient $1$ and the others are zero and are trivially "computed"; you don't need to carry out any square or cube root.

There are some other issues since the sextic extension is often built as a quadratic extension over a cubic extension, but the reasoning is the same.