Geodesic
Faster point compression for elliptic curves of $j$-invariant $0$
Matematičeskie voprosy kriptografii, Tome 12 (2021), pp. 115-123.

Voir la notice de l'article provenant de la source Math-Net.Ru

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}^*$. 
@article{MVK_2021_12_a7,
     author = {D. I. Koshelev},
     title = {Faster point compression for elliptic curves of $j$-invariant $0$},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {115--123},
     publisher = {mathdoc},
     volume = {12},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_a7/}
}
TY  - JOUR
AU  - D. I. Koshelev
TI  - Faster point compression for elliptic curves of $j$-invariant $0$
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 115
EP  - 123
VL  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_a7/
LA  - en
ID  - MVK_2021_12_a7
ER  - 
%0 Journal Article
%A D. I. Koshelev
%T Faster point compression for elliptic curves of $j$-invariant $0$
%J Matematičeskie voprosy kriptografii
%D 2021
%P 115-123
%V 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_a7/
%G en
%F MVK_2021_12_a7
D. I. Koshelev. Faster point compression for elliptic curves of $j$-invariant $0$. Matematičeskie voprosy kriptografii, Tome 12 (2021), pp. 115-123. http://geodesic.mathdoc.fr/item/MVK_2021_12_a7/

[1] El Mrabet N., Joye M., Guide to Pairing-Based Cryptography, Cryptography and Network Security Series, Chapman and Hall/CRC, New York, 2016

[2] Sakemi Y., Kobayashi T., Saito T., Wahby R., Pairing-friendly curves, IETF draft, 2021

[3] Bowe S., BLS12-381: New zk-SNARK elliptic curve construction, Zcash Company blog: , 2017 https://z.cash/blog/new-snark-curve/

[4] Groth J., “On the size of pairing-based non-interactive arguments”, EUROCRYPT 2016, Lect. Notes Comput. Sci., 9665, 2016, 305–326 | DOI

[5] Khabbazian M., Gulliver T., Bhargava V., “Double point compression with applications to speeding up random point multiplication”, IEEE Trans. Computers, 56:3 (2007), 305–313 | DOI | MR | Zbl

[6] Silverman J., The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, 106, Springer, New York, 2009, 533 pp. | DOI | Zbl

[7] Koshelev D., “New point compression method for elliptic $\mathbb{F}{q^2}$-curves of $j$-invariant $0$”, Finite Fields and Their Applications, 69 (2021), 101774 | DOI | MR | Zbl

[8] Cohen H. et al., Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and Its Applications, 34, Chapman and Hall/CRC, New York, 2005

[9] Liedtke C., “Algebraic surfaces in positive characteristic”, Birational Geometry, Rational Curves, and Arithmetic, Simons Symposia, Springer, New York, 2013, 229–292 | MR | Zbl

[10] Cho G. et al., “New cube root algorithm based on the third order linear recurrence relations in finite fields”, Designs, Codes and Cryptography, 75:3 (2015), 483–495 | DOI | MR | Zbl

[11] Koshelev D., Magma code, , 2021 https://github.com/dishport/Faster-point-compression-for-elliptic-curves-of-j-invariant-0