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}^{\ast }$) of $j$-invariant $0$. It is based on ${\mathbb{F}}_q$-rationality of some generalized Kummer surface $G{K}_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 $($i.e., conics over the function field ${\mathbb{F}}_q(t))$ to obtain explicit and quite simple formulas of a birational ${\mathbb{F}}_q$-isomorphism between $G{K}_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 G{K}_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 $$ coordinate, which requires two exponentiations in $$.