Eurocrypt 2013 : Number Theory Session

The number theory session consisted of three talks. One by Joux on the DLP, one by people from Microsoft Redmond on Genus 2 curves, and one by Bouillaguet and co-workers on breaking systems based on hidden quadratic equations.  In this post I will mainly concentrate on the first one, and make a small comment on the second. The third talk was very interesting, and basically concluded that the systems considered in this work should not be considered secure.

Joux presented his work on the medium prime case of DLP in a finite field. He first outlined the basis Function Field Sieve method of Joux and Lercier for solving such DLPs: If the finite field is of size p^k, for p of size L_p^k(1/3), then one selects two polynomials f1(x) and f2(x) of degree d1 and d2 respectively such that d1*d2>k and such that

x-f1(f2(x))

is divisible, modulo p, by an irreducible factor of degree exactly k.

The attacker then selects a smoothness basis of x-a and y-a, and sets y=f2(x), and x=f1(y). With this identification the bivariate linear polynomial

x y + a y + b x + c

can be expressed either as a polynomial in x, or a polynomial in y. When both such polynomials split over the factor base one obtains a relation.

The basic idea of Joux's new method was to apply the technique used when the field can be expressed as a Kummer extension, to all extensions. Namely to fix on y=x^d1. Joux then showed that when one obtains a single relation one can amplify this to many relations using the substitution x = v X for some v. A similar trick working when we consider the other side of the relation. Thus relation finding becomes a task of taking known factorizations and matching them up. This produces a great improvement in the so-called sieving step; in fact eliminating the need for sieving entirely.

Joux ended with discussing his recent work on charactereristic two discrete logarithms; which we have discussed elsewhere in this blog. He presented a new world record; announced in the last week of solving the DLP in a finite field of 6168 bits.

In the next talk Craig Costello presented some interesting performance improvement to arithmetic on genus two curves; obtaining some very impressive results. He presented two implementations; one based on general arithmetic using a four dimensional GLV style trick, and the second based on a Montgomery ladder technique based on the Kummer surface. He left with a tantalising open problem which was to apply GLV style methods to the Kummer surface. This looks very interesting, and a possible place to start this line of work would be to see what can be done in the simpler case of elliptic curves, where both GLV and the Kummer surface are easier to understand