On the first fall degree of summation polynomials (Q2009417)

This paper gives a bound on the first fall degree of the polynomial system arising from the Weil descent along Semaev's summation polynomials. The bound improves a previous one due to \textit{C. Petit} and \textit{J.-J. Quisquater} [Lect. Notes Comput. Sci. 7658, 451--466 (2012; Zbl 1292.94127)]. This is of interest in the application of Gröbner bases to the cryptanalysis of the Elliptic Curve Discrete Logarithm Problem and so the new bound \lq \lq allows us to sharpen the asymptotic run time of the index calculus algorithm for the ECDLP.'' Section 2 remembers the notion of first fall degree of a polynomial system (Definitions 2.1 and 2.2) following the terminology of Hodges, Petit and Schlather [\textit{T. J. Hodges} et al., Finite Fields Appl. 30, 155--177 (2014; Zbl 1355.13020)]. Section 3 begins summarizing the m-summation polynomial of \textit{I. Semaev} [``Summation polynomials and the discrete logarithm problem on elliptic curves'', IACR Cryptology ePrint Archive (2004; \url{https://eprint.iacr.org/2004/031.pdf})], \(S_m(x_1,\dots , x_n)\in K[x_1,\dots , x_n]\)\, on an elliptic curve \(E\)\, defined over a finite field \(K\). The paper takes \(K=F_{2^n}\)\, and describes the Weil descent along the summation polynomial \(S_{m+1}(x_1,\dots , x_n, c)\)\, with \(c\in F_{2^n}\). Theorem 3.2 proves that the first fall degree is less or equal to \(m^2-m+1\), so improving the bound \(m^2+1\)\, of Petit and Quisquater. Finally, Section 4 shows the results of an explicit computation for \(m=2,3,4\)\, using Magma (see Table 1).