Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity (Q908042)

The discrete logarithm problem (DLP), defined in a finite cyclic group \(G\)\,of order \(N\),\, was proposed as a cryptographic tool in the classical paper of \textit{W. Diffie} and \textit{M. E. Hellman} [IEEE Trans. Inf. Theory 22, 644--654 (1976; Zbl 0435.94018)]. The originally proposed group was \(G=\mathbb{F}_q^{*}\), the multiplicative group of a finite field \(\mathbb{F}_q\). However the index-calculus algorithm, see [\textit{L. Adleman}, ``A subexponential algorithm for the discrete logarithm problem with applications to cryptography'', in: Proceedings of the 20th Annual Symposium on Foundations of Computer Science, FOCS 1979, 55--60 (1979)] and its later refinements provided a subexponential attack to the DLP in such a group. The computational complexity of those attacks was \[ L_N(\alpha)=\exp((c+o(1))(\log N)^{\alpha}(\log\log N)^{1-\alpha}),\quad 0<\alpha<1,\;c>0. \] In the authors' words ``By 2006, \(L_N(1/3)\) complexity was achieved for all finite fields. In 2013, the situation changed for small characteristic fields and much faster algorithms appeared for this case''. The aim of this paper is to give a survey of the those algorithms. The paper considers the DLP in a field \(\mathbb{F}_{q^k}\), with \(k\) large. Sections 3 and 4 recall the algorithms of Hellman-Reyneri and Coppersmith and Section 5 describes a variation of the function field sieve algorithm due to \textit{A. Joux} and \textit{R. Lercier} [Eurocrypt 2006, Lect. Notes Comput. Sci. 4004, 254--270 (2006; Zbl 1140.94349)], which allows a complexity of \(L_{q^k}(1/3)\) (for any finite field). Section 6 summarizes the new approaches allowing, for small characteristic fields, a quasi-polynomial algorithm, see [\textit{R. Barbulescu} et al., Eurocrypt 2014, Lect. Notes Comput. Sci. 8441, 1--16 (2014; Zbl 1326.11080)]. Finally Section 6 discusses some open problems, such as ``to find a truly polynomial time algorithm rather than a quasi-polynomial one'' and ``generalize these algorithms to the case of larger characteristic fields''.