Index calculus in the trace zero variety (Q895005)

Let \(E\) be an elliptic curve defined by a Weierstrass equation over a finite field \(F_q\) and \(\phi\) the Frobenius endomorphism. For a field extension \(F_{q^n} / F_q\) of degree \(n > 1\), the trace map \(Tr : E(F_{q^n}) \rightarrow E(F_q)\) is defined by the correspondence \(P\mapsto P + \phi(P) + \cdots + \phi^{n-1}(P)\). When \(n\) is prime, the kernel of the trace map is called the \textit{trace zero subgroup} of \(E(F_{q^n})\). It is denoted by \(T_n\) and is isomorphic to the group of \(F_q\)-rational points of the \textit{trace zero variety} \(V_n\), which is an \((n-1)\)-dimensional subvariety of the Weil restriction of \(E\). Using trace zero varieties in cryptographic protocols presents some advantages with respect to elliptic curves. The paper under review deals with the application of Gaudry's index calculus algorithm for abelian varieties to solve the discrete logarithm problem in \(T_n\). It also gives an analysis of this algorithm asymptotically in \(n\) and \(q\), and shows that the complexity is exponential in \(n\). The practical cases of the field extensions of degree 3 or 5 are particularly treated and Magma experiments are presented. Furthermore, the index calculus attack on the DLP in \(T_n\) is compared with other known attacks.