Discrete Logarithms

Two results have appeared in the last week in the field of discrete logarithms for finite fields of small characteristic which are quite surprising.  Before discussing the results let me first just set the mathematical scene.

A finite field is given by a prime number p, called the characteristic, and a positive integer n. The finite field is then the set of all polynomials with coefficients in the set {0,...,p-1} of degree strictly less than n. We can add elements in the set by just adding them as polynomials and reducing the coefficients of the resulting polynomial modulo p, so they like back in the range {0,...,p-1}. Multiplication is a bit more tricky, we need to find an irreducible polynomial f of degree n modulo p; then multiplication is given by multiplication modulo f and p. It turns out that the choice of f does not really matter, so we can think of the field as being given by p and n.

So thats finite fields in a paragraph; now what about discrete logarithms? To define a discrete logarithm one picks an element g in the field and then one picks a secret random integer x and one computes 

h=g^x 

in the field. The discrete logarithm problem is given g and h, find x.

So how hard is this problem? For many years the best known algorithm has either been the Number Field Sieve (for large p and small n), or the Function Field Sieve (for small p and large n). If we let 

q=pⁿ

Then the important measure of difficulty is the so-called L function, which is roughly

L(a) = O(exp((log q)^a (log loq q)^1-a))

To get a feel for L, we note that L(1) is the run time of a fully exponential algorithm and L(0) is the run time of a polynomial time algorithm. When public key cryptography started in the mid 1970's the run time of both the best factoring and the best discrete logarithm algorithm was essentially L(1), although this was quickly reduced to L(1/2) for both problems with the advent of the quadratic sieve. For factoring we replace q by N (the number to be factored) in the expression above.

The next big advance was the invention of the number field sieve which showed that factoring and discrete logarithms (for large p), could be solved in time L(1/3). Around the same time the function field sieve was invented which could solve discrete logarithms for small characteristic finite fields in time L(1/3) as well. Notice, how factoring and discrete logarithms are linked? An advance in one field usually leads to an advance in another and the two complexities are roughly always "in step".

So for the last 20 years we have picked key sizes for factoring and discrete logarithm systems based on the fact that the fastest algorithm runs in time L(1/3). Although for small characteristic finite fields were always considered easier, the extra speed essentially came from the hidden constants rather than the argument of the L function.

But in the last week we have seen two results. The first announcement by Gologiu, Granger (an ex-PhD student from Bristol), McGuire and Zumbragel has demonstrated that one can find discrete logarithms in the finite field of 2¹⁹⁷¹ in practice. Note, this is over twice the bit-length of the best record for factoring or discrete logarithms in large characteristic fields.  The second announcement was by Antoine Joux of a (related) method to solve discrete logarithms in small characteristic fields which runs in time L(1/4).

So apart from being two amazing breakthroughs in implementation and analysis of algorithms, what does this really mean for cryptography?

Firstly, the discrete logarithm problem in small finite fields should not be used for cryptography. We kind of new this already. So nothing surprising there.

Secondly, the two announcements focus on the case of p=2, but the results should pass over to p=3 quite easily. This should signal the death knell for pairing based cryptography on Type-1 curves in small characteristic. Whilst such curves have not been used in commercial systems for a long time, they have been the subject of many academic papers. Hopefully, the above announcements will force the academics working on this topic to move to more useful areas of research.

Thirdly, and this is pure speculation. History has shown that an advance in discrete logarithms is often followed by an advance in factoring. There is no reason to expect such an advance to follow this time; but then again there is no reason not to expect it either. If we can find an algorithm for factoring which runs in time L(1/4) then this will mean that many of the systems we rely on for security will need to be upgraded. This upgrading, to systems which do not depend on factoring, is already being conducted by many organizations.

If we cannot rely on systems based on factoring large numbers, what can we rely on? It turns out that we have known the answer for around 20 years already, the answer lies in elliptic curves. If you want to find out more about elliptic curves then see the two classic text books in the area. Elliptic curves are already deployed in a number of places; in your phone, in the Playstation and XBox, in your browser and many other places.