New results on the discrete logarithm problem in finite fields of small characteristic

Two recent papers on eprint have made tremendous progress on the discrete logarithm problem in the multiplicative group of a finite field of characteristic two. The papers are:

The story starts with Antoine Joux’s paper “Faster index calculus for the medium prime case: Application to 1175-bit and 1425-bit finite fields” which is accepted to Eurocrypt 2013 and can be found at Cryptology ePrint Archive: Report 2012/720. This paper is about the “medium prime case” (i.e., discrete logs in F_{p^n} where p and n are both “large” (e.g., n approx log(p)). The paper uses a factor base consisting of “linear polynomials” (read the paper for the precise details). It introduced a key idea (called “pinpointing” in that paper) which is an alternative approach to sieving.

The recent papers are motivated by the above work, but have two major differences. First is to consider composite degree finite fields F_{2^{mk}} as “medium prime” fields F_{q^k} where q = 2^m. Second is to find one smooth relation and then generate many more by simple polynomial transformations (the two papers differ in the details).

The resulting algorithms are then very different from previous approaches: The typical scenario would involve a factor base of size L_{2^{mk}}( 1/3, c ), and the cost of generating relations would dominate the computation. Now, the factor base is rather small and generating the relations is extremely fast (even polynomial-time). The linear algebra still must be performed, but this is not too bad since the factor base is small.

The problem now is the final stage of the index calculus algorithm: Writing the problem instance in terms of the factor base. Since the factor base is now very small, this problem has become much harder. The serious work in both papers is to provide solutions to this problem and to determine the complexity. The details differ and I will not go into them now (partly because I am still digesting them myself). Gologlu et al claim L_{2^{mk}}( 1/3, c ) while Joux claims a very unexpected running time of L_{2^{mk}}( 1/4 + o(1), c ) field operations (note that this is not the same as L( 1/4, c + o(1))). Both results are heuristic. Joux’s paper is still very sketchy and contains many typographical errors, but if correct then this will be the first sub-L( 1/3 ) algorithm known in the literature — a major advance!

For concreteness, the above discussion is restricted to characteristic equal to 2. However, the methods also apply to any small characteristic.

It is worth stressing that both papers apply to composite field extensions F_{2^{mk}} where m and k satisfy some relationship. The case of prime fields F_{2^k} can of course be embedding in F_{2^{mk}} for a suitable m. Asymptotically this might mean that field sizes for discrete logarithm cryptography need to be adjusted, but it seems that fields F_{2^k} where k is prime and 1000 < k < 2000 are probably not currently weakened by these ideas. However, in pairing based cryptography using supersingular curves over F_{2^k} of genus 1 or 2, one maps into fields of the form F_{2^{4k}} or F_{2^{12k}} (and, in char 3, F_{3^{6k}}) for prime values for k. Hence, one consequence of the new algorithms may be that characteristic 2 and 3 fields are not appropriate for pairing-based cryptography.

— Steven Galbraith

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to New results on the discrete logarithm problem in finite fields of small characteristic

  1. Laura Hitt says:

    Here are articles from the Irish Sunday Times and Science Spinning “reporting that a team of mathematicians from UCD have set a world record for the largest discrete log problem ever solved – which has consequences for cryptology and online security.”
    http://seanduke.com/2013/03/04/ucd-team-break-cryptography-world-record/
    http://www.math.ie/ST3March2013.jpg

  2. Laura Hitt says:

    Just saw that Rob Granger announced he and co-workers set a new record of a DLP for composite degree extensions in characteristic two, solving DLPs in GF(2^6120)…? Steven, can you tell us any more info given your network of connections? ;-)

    Exciting times!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s