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}^*$.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint. MINOR revision.
 Keywords
 finite fieldspairingbased cryptographyelliptic curves of $j$invariant $0$point compression
 Contact author(s)
 dimitri koshelev @ gmail com
 History
 20210911: last of 5 revisions
 20200106: received
 See all versions
 Short URL
 https://ia.cr/2020/010
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/010, author = {Dmitrii Koshelev}, title = {Faster point compression for elliptic curves of $j$invariant $0$}, howpublished = {Cryptology ePrint Archive, Paper 2020/010}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/010}}, url = {https://eprint.iacr.org/2020/010} }