I am struggling to understand how to perform a sextic twist over a BN elliptic curve. This is what I understood so far:

Let's consider a BN elliptic curve: $$ E: y^2=x^3+b $$ And let's consider a point $Q \in E(F_{p^{12}}) $. What I would like to do is to "easily" go from/to $Q \in E(F_{p^{12}})$ to/from $Q' \in E'(F_{p^{2}})$, where $Q'$ is the sextic twist defined as $$ E': y^2=x^3+b/\xi $$ In fact I can use this isomorphism (I guess) to move from/towards $E$ and $E'$: $$ \psi: E'(F_{p^2}) \rightarrow E(F_{p^{12}}) $$ $$ \psi((x',y')) = (\xi^{1/3}x',\xi^{1/2}y') $$ $$ \psi^{-1}(x,y) = \left(\frac{x}{\xi^{1/3}},\frac{y}{\xi^{1/2}}\right) $$ My questions are:

  1. Is the isomorphism I wrote correct?
  2. Is $\xi$ an integer number in $F_p$?
  3. Can I choose any value I want for $\xi$? I guess that I should choose it so that $\xi^{1/3}$ and $\xi^{1/2}$ are integers, but I'm not sure...

1 Answer 1

  1. The map $\psi(x',y')$ is correct, but it is a homomorphism and not an isomorphism. The two curves have different numbers of points and so there can be no isomorphism between them. One can check that the map is a well-defined as for $x',y',\xi\in\mathbb F_{p^2}\Rightarrow \xi^{1/3}x',\xi^{1/2}y'\in\mathbb F_{p^{12}}$ and $$y'^2=x'^2+\frac b\xi\Rightarrow (\xi^{1/2}y')^2=(\xi^{1/3}x')^3+b.$$ The homomorphism can be tediously checked by working through the addition formulae (note that the slope formula will scale by a factor of $\xi^{1/6}$). The inverse $\psi^{-1}$ function only lands on $E'(\mathbb F_{p^2})$ if $x/\xi^{1/3}$ and $y/\xi^{1/2}$ are both in $\mathbb F_{p^2}$ which will not be the case for a general point of $E(\mathbb F_{p^{12}})$. It will however be correct for any point on the subgroup of $E(\mathbb F_{p^{12}})$ that is the image of $\psi$.

  2. and 3. For any value $\xi$ in $\mathbb F_{p^2}$ the map is defined. However, you should choose $\xi$ that is neither a square (in particular not an element of $\mathbb F_p$) nor a cube in $\mathbb F_{p^2}$ otherwise the image of $\psi$ will lie in $\mathbb F_{p^6}$ or $\mathbb F_{p^4}$ respectively and pairings between points in the image of $\psi$ will all be equal to 1.

  • $\begingroup$ Worth noting that the map can be clearly defined over the algebraic closure, where it is clearly an isomorphism.. (already over $F_{p^{12}}$). $\endgroup$
    – Fractalice
    Oct 19, 2021 at 12:54
  • $\begingroup$ @Fractalice Good point, I've added some ground field notation to make this explicit. Formally $$\psi: E(\overline{\mathbb F_p})\to E'(\overline{\mathbb F_p})$$ and $$\psi^{-1}:E'(\overline{\mathbb F_p})\to E(\overline{\mathbb F_p})$$ are both isomorphisms. For cryptographic purposes though we will always want to restrict to something finite. $\endgroup$
    – Daniel S
    Oct 19, 2021 at 18:45
  • 1
    $\begingroup$ I've modified the MathJax/LaTex in the above comment so that it renders. I hope the overline applies to what's intended. Where I stand the MathJax can be viewed with right click/Show Math As/TeX Commands. $\endgroup$
    – fgrieu
    Feb 14 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.