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

D. I. Koshelev

Matematičeskie voprosy kriptografii, Tome 12 (2021), pp. 115-123

Résumé

The article provides a new double point compression method (to $2\lceil\log_2(q)\rceil + 4$ bits) for an elliptic curve $E_b : y^2 = x^3 + b$ of $j$-invariant $0$ over a finite field $\mathbb{F}_{q}$ such that $q\equiv{1}\pmod{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_b(\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}\pmod{4}$, $q\not\equiv{1}\pmod{27}$ this may 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}^*$.