Cryptology ePrint Archive: Report 2019/1048

A new elliptic curve point compression method based on $\mathbb{F}_{\!p}$-rationality of some generalized Kummer surfaces

Dmitrii Koshelev

Abstract: In the article we propose a new compression method (to $2\log_2(p) + 3$ bits) for the $\mathbb{F}_{\!p^2}$-points of an elliptic curve $E_b\!: y^2 = x^3 + b$ (for $b \in \mathbb{F}_{\!p^2}^*$) of $j$-invariant $0$. It is based on $\mathbb{F}_{\!p}$-rationality of some generalized Kummer surface $GK_b$. This is the geometric quotient of the Weil restriction $R_b := \mathrm{R}_{\: \mathbb{F}_{\!p^2}/\mathbb{F}_{\!p}}(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}_{\!p}(t)$) to obtain explicit and quite simple formulas of a birational $\mathbb{F}_{\!p}$-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}_{\!p^2}) = R_b(\mathbb{F}_{\!p})$ we find an inverse image of the natural map $R_b \to GK_b$ of degree $3$, i.e., we extract a cubic $\mathbb{F}_{\!p}$-root. For $p \not\equiv 1 \: (\mathrm{mod} \ 27)$ this is just a single exponentiation in $\mathbb{F}_{\!p}$, hence the new method seems to be much faster than the classical one with $x$ coordinate, which requires two exponentiations in $\mathbb{F}_{\!p}$.

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 26 Oct 2019

Contact author: dishport at ya ru

Available format(s): PDF | BibTeX Citation

Version: 20191026:114030 (All versions of this report)

Short URL: ia.cr/2019/1048


[ Cryptology ePrint archive ]