Compression for trace zero points on twisted Edwards curves (Q269104)

This paper proposes two optimal compression representations for trace zero subgroups of elliptic curves in twisted Edwards form, adapting previous works of the second author and M. Massierer.NEWLINENEWLINEGiven an elliptic curve \(E\)\, (or the Jacobian of an hyperelliptic curve) defined over a finite field \(\mathbb{F}_q\),\, the subgroup of points of \(E\)\, over an extension \(\mathbb{F}_{q^n}\)\, with trace zero over \(E(\mathbb{F}_q)\),\, was proposed for cryptographic use by \textit{G. Frey} [in: Finite fields and applications. Proceedings of the fifth international conference on finite fields and applications \(F_q5\), University of Augsburg, Germany, August 2--6, 1999. Berlin: Springer. 128--161 (2001; Zbl 1015.94545)], due to its good computational properties. Similar computational advantages also motivated the proposal of the Edwards model of elliptic curves and their generalization, the twisted Edwards curves, proposed by \textit{D. J. Bernstein} et al. [Lect. Notes Comput. Sci. 5023, 389--405 (2008; Zbl 1142.94332)].NEWLINENEWLINESection 1 collects the necessary ingredients about Edwards curves, trace zero subgroups and representations. Section 2 presents the first representation which adapts to twisted Edwards curves the ideas of \textit{E. Gorla} and \textit{M. Massierer} [Des. Codes Cryptography 75, No. 2, 335--357 (2015; Zbl 1319.14033)]. This representation uses Weil restriction and Semaev's summation polynomials. The paper provides efficient compression and decompression algorithms (Algorithms 1 and 2) and it gives explicit equations and timing of an implementation in Magma for \(n=3\)\, (Subsection 2.1) and \(n=5\)\, (Subsection 2.2), comparing those times with the obtained for Weiertrass models.NEWLINENEWLINEThe second representation, based on the work of \textit{E. Gorla} and \textit{M. Massierer} [``An optimal representation for the trace zero subgroup'', \url{arxiv:1405.2733}], and studied in Section 3, uses rational functions. As for the first representation the cases \(n=3,\,\, n=5\)\, are worked in detail.