Point compression for the trace zero subgroup over a small degree extension field (Q2340180)

The article is devoted to the study of the trace zero variety of an elliptic curve defined over the finite field \(\mathbb{F}_q\) of \(q\) elements. More precisely, a description of the \(\mathbb{F}_q\)-rational points of the trace zero variety of a given elliptic curve is obtained, a new representation of these points is proposed, and an algorithm for compression and decompression is described and analyzed. Let \(E\) be an elliptic curve defined over \(\mathbb{F}_q\). For a field extension \(\mathbb{F}_q|\mathbb{F}_{q^n}\), denote by \(E(\mathbb{F}_{q^n})\) the group of \(\mathbb{F}_{q^n}\)-rational points of \(E\). The kernel of the trace map \(\varphi:E(\mathbb{F}_{q^n})\to E(\mathbb{F}_q)\) is the \textit{trace zero subgroup} \(T_n\) of \(E(\mathbb{F}_{q^n})\). By Weil restriction the points of \(T_n\) can be viewed as the \(\mathbb{F}_q\)-rational points of an abelian variety \(V\) of dimension \(n-1\) defined over \(\mathbb{F}_q\), which is called the \textit{trace zero variety}. In the paper under review, a new representation for the elements of \(T_n\) is discussed. Choosing a basis of \(\mathbb{F}_{q^n}\) as \(\mathbb{F}_q\)-vector space, a point \(P\in T_n\) is represented by its first \(n-1\) coordinates \((X_0,\dots,X_{n-2})\in\mathbb{F}_q^{n-1}\) in this basis, together with an equation in \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\) which vanishes on the coordinates of any \(P\in T_n\), where \(x_0,\dots,x_{n-1}\) are indeterminates over \(\mathbb{F}_q\). This representation, although not injective, identifies a small number of points, and is of optimal size. In order to obtain the equation for the representation of the elements of \(T_n\), the authors rely on the Semaev summation polynomials [\textit{I. Semaev}, ``Summation polynomials and the discrete logarithm problem on elliptic curves'', preprint, \url{http://eprint.iacr.org/2004/031.pdf} (2004)]. These polynomials provide conditions on the \(x\)-coordinates of a finite number of points on an elliptic curve summing to \(\mathcal{O}\). The authors consider such polynomials applied to the Frobenius conjugates of any point \(P\in T_n\). Further, taking into account that each Semaev summation polynomial is a symmetric element of \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\), it is expressed in terms of the elementary symmetric polynomials \(\mathbb{F}_q[z_1,\dots,z_n]\). As a consequence, a \textit{compression} of the representation of the points of \(T_n\) is obtained by computing the elementary symmetric polynomials in the \(x\)--coordinates of the Frobenius conjugates of a given \(P\in T_n\). The \textit{decompression} is obtained by using the ``symmetrized'' version of the corresponding Semaev summation polynomial. Finally, explicit equations are given for extensions of degree 3 and 5, and the cost of compression and decompression is analyzed.