[Resource Topic] 2020/010: Faster point compression for elliptic curves of $j$-invariant $0$

Welcome to the resource topic for 2020/010

Title:
Faster point compression for elliptic curves of j-invariant 0

Authors: 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}^*.

ePrint: https://eprint.iacr.org/2020/010

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .