7
$\begingroup$

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...
$\endgroup$
0
$\begingroup$
  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/y^{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.

$\endgroup$
2
  • $\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 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 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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