Paper 2019/1048

New point compression method for elliptic $\mathbb{F}_{\!q^2}$-curves of $j$-invariant $0$

Dmitrii Koshelev

Abstract

In the article we propose a new compression method (to $2\lceil \log_2(q) \rceil + 3$ bits) for the $\mathbb{F}_{\!q^2}$-points of an elliptic curve $E_b\!: y^2 = x^3 + b$ (for $b \in \mathbb{F}_{\!q^2}^*$) of $j$-invariant $0$. It is based on $\mathbb{F}_{\!q}$-rationality of some generalized Kummer surface $GK_b$. This is the geometric quotient of the Weil restriction $R_b := \mathrm{R}_{\: \mathbb{F}_{\!q^2}/\mathbb{F}_{\!q}}(E_b)$ under the order $3$ automorphism restricted from $E_b$. More precisely, we apply the theory of conic bundles $\big($i.e., conics over the function field $\mathbb{F}_{\!q}(t)\big)$ to obtain explicit and quite simple formulas of a birational $\mathbb{F}_{\!q}$-isomorphism between $GK_b$ and $\mathbb{A}^{\!2}$. Our point compression method consists in computation of these formulas. To recover (in the decompression stage) the original point from $E_b(\mathbb{F}_{\!q^2}) = R_b(\mathbb{F}_{\!q})$ we find an inverse image of the natural map $R_b \to GK_b$ of degree $3$, i.e., we extract a cubic root in $\mathbb{F}_{\!q}$. For $q \not\equiv 1 \: (\mathrm{mod} \ 27)$ this is just a single exponentiation in $\mathbb{F}_{\!q}$, hence the new method seems to be much faster than the classical one with $x$ coordinate, which requires two exponentiations in $\mathbb{F}_{\!q}$.