New point compression method for elliptic \(\mathbb{F}_{q^2}\)-curves of \(j\)-invariant 0 (Q1995209)

In Elliptic Curve Cryptography an usual tool is a compression representation of a point \((x,y)\)\, of the underlying elliptic curve defined over a finite field \(\mathbb{F}_q\). Usually this is done taking the \(x\)-coordinate plus a single bit. The present paper proposes a new method for ordinary elliptic curves \(E_b: y^2=x^3+b\),\, defined over \(\mathbb{F}_{q^2}\),\,field of characteristic \(p\equiv 1 \bmod 3\),\, method that \lq \lq seem to be much faster than the classical one with \(x\)-coordinate, which requires two exponentiations in \(\mathbb{F}_q\).'' (for the decompression stage).\par The proposed method uses the Weil restriction \(R_b= R_{\mathbb{F}_{q^2}/\mathbb{F}_q}(E_b)\)\, and the generalized Kummer surface \(GK_b=R_b/[\omega]_2\), with \([\omega]_2\) the automorphism induced by a cubic root of 1, \(\omega \in \mathbb{F}_p\).\par \(GK_b\)\, is proved to be \(\mathbb{F}_{q^2}\)-rational and the paper, applying the theory of conic bundles, find a birational \(\mathbb{F}_q\)-isomorphism \(GK_b\approx \mathbb{A}^2\),\, which gives the looked compression. \par To recover the original point of the curve one need to compute one cubic root in \(\mathbb{F}_q\)\, which, for \(q\not \equiv 1 \bmod 27\),\, requires one exponentiation in \(\mathbb{F}_q\).\par Sections 1 and 2 gather the necessary mathematical background and some auxiliary results. The proposed compression is showed in Section 3. Theorem 12 proves (for \(q=p)\)\, that \(GK_b\)\, is \(\mathbb{F}_p\)-rational and gives the birational isomorphism \(GK_b\approx \mathbb{A}^2\).\par Section 3.1 instantiates the compression method to a family of curves, family including the pairing-friendly curve BLS12-381, [\url{https://z.cash/blog/new-snark-curve/}], and studies the complexity of the compression and decompression stages, see Table 1.