Paper 2020/010

Faster point compression for elliptic curves of $j$-invariant $0$

Dmitrii Koshelev

Abstract

The article provides a new double point compression method (to $2\lceil {\log }_2(q)\rceil +4$ bits) for an elliptic ${\mathbb{F}}_q$-curve $E_b:y^2=x^3+b$ of $j$-invariant $0$ over a finite field ${\mathbb{F}}_q$ such that $q\equiv 1(\mathrm{mod}3)$. More precisely, we obtain explicit simple formulas transforming the coordinates $x_0,y_0,x_1,y_1$ of two points $P_0,P_1\in E({\mathbb{F}}_q)$ to some two elements of ${\mathbb{F}}_q$ with four auxiliary bits. In order to recover (in the decompression stage) the points $P_0,P_1$ it is proposed to extract a sixth root $\sqrt[6]{Z}\in {\mathbb{F}}_q$ of some element $Z\in {\mathbb{F}}_q$. It is known that for $q\equiv 3(\mathrm{mod}4)$, $q\not\equiv 1(\mathrm{mod}27)$ this can be implemented by means of just one exponentiation in ${\mathbb{F}}_q$. Therefore the new compression method seems to be much faster than the classical one with the coordinates $x_0,x_1$, whose decompression stage requires two exponentiations in ${\mathbb{F}}_q$. We also successfully adapt the new approach for compressing one ${\mathbb{F}}_{q^2}$-point on a curve $E_b$ with $b\in {\mathbb{F}}_{q^2}^{\ast }$.