**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}$.

**Category / Keywords: **implementation / pairing-based cryptography, elliptic curves of $j = 0$, point compression, Weil restriction, generalized Kummer surfaces, rationality problems, conic bundles, cubic roots, singular cubic surfaces

**Date: **received 15 Sep 2019, last revised 2 Dec 2020

**Contact author: **dishport at ya ru

**Available format(s): **PDF | BibTeX Citation

**Version: **20201202:160520 (All versions of this report)

**Short URL: **ia.cr/2019/1048

[ Cryptology ePrint archive ]