Quasi-polynomial-time algorithm for discrete logarithm in finite fields of small/medium characteristic

A major breakthrough this week has been the announcement by Razvan Barbulescu, Pierrick Gaudry, Antoine Joux and Emmanuel Thomé of a quasi-polynomial-time DLP algorithm for finite fields. The paper is available here

The algorithm applies to finite fields of the form $GF( q^k )$ , where $q$ is a prime power and where $q \approx k$ . We represent this field as $GF( q )[x]/(F(x))$ where $F(x)$ is an irreducible polynomial of degree $k$ such that $F(x)$ divides $h_1(x) x^q - h_0(x)$ , where $h_0$ and $h_1$ are linear or quadratic. Since this polynomial has degree $q+1$ or $q+2$ it follows that we need $k \le q+2$ .

Following the previous work by Joux (see Section 4), the factor base is the set of linear or quadratic polynomials over $GF( q^2 )$ . First one finds relations among the linear polynomials in polynomial-time $O( q^5 )$ by substituting into the systematic equation $x^q - x = \prod_{a \in GF(q)} (x - a)$ linear fractional transformations over $GF( q^2 )$ in $x$ (this is where the group $PGL_2( GF( q^2 ))$ enters; such transformations are also called homographies or Mobius transformations). One gets a cubic polynomial in $x$ equal to a product of linear polynomials. If the cubic polynomial splits (which happens with probability $1/6$ ) then one has a relation. One needs $O( q^2 )$ such relations. Sparse linear algebra (each row has $O( q )$ non-zero entries out of $O( q^2 )$ ) allows to express the discrete logarithms of linear polynomials with respect to any fixed linear polynomial $(x-b)$ that generates the field. The cost of the linear algebra is $O( q^5 )$ operations in the ring $Z_{q^k-1}$ .

This is not enough. We also need quadratic polynomials in our factor base. This is explained in Section 4.3 of Joux’s paper. One can handle the issue by solving $O( q^2 )$ systems of equations (each taking $O( q^5 )$ operations). Hence, the overall complexity of the first stage is $O( q^7 )$ . This is polynomial time in the input size $\log( q^k ) = k \log(q) = q \log(q)$ (as $k \approx q$ ).

The major innovation of the new paper is a new approach for the descent procedure. This is when you take a polynomial $P(x)$ , corresponding to the original DLP instance, and want to express it as a product of elements in the factor base. The idea is to recycle ideas from the first step. Suppose $\deg(P(x)) = D$ . One substitutes into the systematic equation a linear fractional transformation $x = (a P + b)/(c P + d)$ over $GF( q^2 )$ . One now has on the left hand side a polynomial in $x$ of degree $3D$ and on the right hand side a product of linear terms of the form $(P - a)$ for $a \in GF( q^2 )$ . With probability around $1/6!$ the left hand side splits into a product of polynomials of degree at most $D/2$ . If that happens we have a relation. One needs $O( q^2 )$ relations and then one can perform linear algebra to eliminate all $(P-a)$ terms on the right hand side, except for $P$ itself. We therefore express $P$ as a product of $O( q^2 D )$ polynomials of smaller degree (the $q^2$ term arises as we have combined $O( q^2 )$ relations, each of which features at most $D$ polynomials).

One then proceeds recursively. Since the degree is initially $D=k$ , but drops from $D$ to $D/2$ at each stage, there are $\log(k)$ levels of recursion. The total number of polynomials that arise is an enormous $(q^2 D)^{O( \log(k) )}$ . But this is quasi-polynomial in the input size.

And there you have it — surprisingly simple!

Much work will be done to improve the descent step. In practice one will begin with subexponential smoothing as in the function field sieve, then employ both the new method and the Groebner basis method due to Joux.

The method is particularly suitable for fields that can already be written in the form $GF( q^k )$ with $q \approx k$ . For example, with the recent records $GF( 2^{6168} )$ we take $q = 2^8 = 256, k = 257$ and work with $GF( q^3 )$ instead of $GF( q^2 )$ for the factor base.

It is interesting to consider the case of prime extensions $GF( 2^p )$ , where $p \approx 1000$ is prime. The traditional function field sieve would be expected to solve such problems in around $2^{80}$ to $2^{90}$ bit operations. For the new approach we need to embed this field into $GF( q^k )$ with $q \approx k$ . The obvious choice is $q = 2^{10}$ . Then the first stage of the algorithm, as we have mentioned, already takes time proportional to $q^7 = 2^{70}$ . The descent step will be much more time-consuming. For example $(q^2 k)^{10} \approx 2^{233}$ . Of course, we expect this can be improved significantly, but for the moment the new method does not seem to beat FFS for fields of this size (much larger $p$ is another story).

For pairing fields such as $GF( 2^{239 * 12} ) = GF( 2^{2868} )$ things are much more risky. Taking $q = 2^{12} = 4096$ and $k = 239$ is already somewhat close to the ideal range. I would not be surprised if this case is broken before the end of the year.

— Steven Galbraith

2 Responses to Quasi-polynomial-time algorithm for discrete logarithm in finite fields of small/medium characteristic

Luca De Feo says:

July 5, 2013 at 5:36 pm

Hi Steven,

You say that a factor base of linear polynomials is not enough, but I can see no mention of this in the BGJT paper. Could you comment more on this?

- ellipticnews says:
  
  July 5, 2013 at 9:55 pm
  
  There was some discussion of this in Paris. Antoine seemed to be of the opinion that linear polynomials are not sufficient, but I am not sure why. I guess that in a few months this will all be more clear, once more computations have been done. I will not be surprised if we eventually can use only linear polynomials, or maybe even fewer (using a “large prime” variation).

	Aurore Guillevic on CRYPTO 2020
	Francisco Rodriguez… on Eurocrypt 2020
	Luca De Feo on Isogeny crypto
	Recent work on pairi… on Kim–Barbulescu variant o…
	ellipticnews on Isogeny-based post-quantum cry…