Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
type: Item
instance of: scholarly article
title: Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
zbMATH Open document ID: 1364.11165
author: Antoine Joux
author: Cécile Pierrot
published in: Designs, Codes and Cryptography
publication date: 2016-02-02T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 6538691
zbMATH Keywords: cryptography
zbMATH Keywords: discrete logarithms
zbMATH Keywords: finite fields
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: s10623-015-0147-6
OpenAlex ID: W2231274371
cites work: Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography
cites work: Computing Discrete Logarithms in $${\mathbb F}_{3^{6 \cdot 137}}$$ and $${\mathbb F}_{3^{6 \cdot 163}}$$ Using Magma
cites work: Function field sieve method for discrete logarithms over finite fields
cites work: Discrete Logarithm in GF(2809) with FFS
cites work: A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
cites work: On a problem of Oppenheim concerning ''Factorisatio Numerorum''
cites work: Fast evaluation of logarithms in fields of characteristic two
cites work: New directions in cryptography
cites work: On the Function Field Sieve and the Impact of Higher Splitting Probabilities
cites work: Q4318705
cites work: Breaking ‘128-bit Secure’ Supersingular Binary Curves
cites work: On the discrete logarithm problem in finite fields of fixed characteristic
cites work: Faster Index Calculus for the Medium Prime Case Application to 1175-bit and 1425-bit Finite Fields
cites work: A New Index Calculus Algorithm with Complexity $$L(1/4+o(1))$$ in Small Characteristic
cites work: Q4737504
cites work: The Function Field Sieve in the Medium Prime Case
cites work: Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms
cites work: The Past, Evolving Present, and Future of the Discrete Logarithm
cites work: Q3840165
cites work: Q3808150
cites work: Key Length Estimation of Pairing-Based Cryptosystems Using η T Pairing
cites work: Factoring polynomials over finite fields: A survey
cites work: Solving sparse linear equations over finite fields
DOI: 10.1007/S10623-015-0147-6
Recommended article: A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
Recommended article: Discrete Logarithm in GF(2809) with FFS
Recommended article: Indiscreet logarithms in finite fields of small characteristic
Recommended article: Q4375624
Recommended article: Faster individual discrete logarithms in finite fields of composite extension degree
Recommended article: Q3615927
Recommended article: Q4847920
Recommended article: Function field sieve method for discrete logarithms over finite fields
Recommended article: Computing Discrete Logarithms
Recommended article: The Number Field Sieve in the Medium Prime Case
description: scientific article; zbMATH DE number 6538691