Day Two of ANTS 2014

The Eleventh Algorithmic Number Theory Symposium took place in rainy GyeongJu, Korea on August 6-11, 2014. The proceedings are available online in the open access LMS Journal of Computation and Mathematics.

The first day contained a number of excellent lectures, but none direct relevant to elliptic curve cryptography. Unfortunately one talk was not given (and another talk was given by a substitute speaker).

Day two of the conference contained all the papers about the discrete logarithm problem.

The morning began with Antoine Joux‘s invited lecture “The discrete logarithm problem in small characteristic finite fields”. The talk began with a general survey of generic DLP algorithms and index calculus methods. He then moved on to discuss the recent work for the DLP in \mathbb{F}_{p^k} for small p and large k. First he explained the general approach, going back to Joux-Lercier (EUROCRYPT 2006) for the “medium-prime case”, of choosing two polynomials f_1(X) and f_2(X) in \mathbb{F}_p[X] of degrees d_1, d_2 respectively, such that f_1( f_2(X)) - X has an irreducible factor of degree k. One then uses a certain diagram of rings to develop an algorithm relying on some heuristics. Antoine explained a case where the heuristics badly fail, and noted that this leads to the greatly improved algorithms in small characteristic.

He then introduced a new and simplified approach to the algorithm, which avoids extending the field (previous approaches took a quadratic or cubic extension for the coefficients of the “homographies”). We explain this approach now.

We are interested in the DLP in \mathbb{F}_{q^k}^*. Let I(X) \in \mathbb{F}_q[X] be an irreducible polynomial of degree k that divides h_1(X^q)X - h_0(X^q), where \deg( h_1(X)), \deg( h_0(X) ) \leq H. Write \mathbb{F}_{q^k} = \mathbb{F}_q[\theta] where \theta is a roots of I(X). The key equation is (1) X^q - X = \prod_{\alpha \in \mathbb{F}_q} (X - \alpha). Choose integer D and set factor base to be polynomials over \mathbb{F}_q in variable \theta of degree \leq D. Let A, B also be polynomials over \mathbb{F}_q in variable \theta of degree \leq D. Substituting A(\theta)/B(\theta) into equation (1) (this is the alternative to using homographies) and doing standard algebra gives B(\theta) \prod_{\alpha \in \mathbb{F}_q} (A(\theta) - \alpha B(\theta) ) = B(\theta) A( h_0(\theta)/h_1(\theta) ) - A(\theta) B(  h_0(\theta)/h_1(\theta) ). The LHS of the equation splits over the factor base. Antoine introduces new notation [ A, B]_D so that the RHS of the equation is [A, B]_D(\theta)/ h_1(\theta)^D. If the numerator of the RHS splits over the factor base then we have a relation. He gives several properties of the polynomial/symbol [ A, B]_D. He then argues that D = 3 is the smallest choice for D for which one can expect to compute enough relations this way. He concludes that the running time of the first stage of the algorithm (to compute the discrete logarithm of everything in the factor base with respect to some single element in the factor base) is O( q^7 ) field operations in \mathbb{F}_q.
The remainder of his talk surveyed four descent strategies and explained how they are all combined to give the full algorithm.

The next talk was “The discrete logarithm problem for exponents of bounded height” presented by Sam Scott (joint work with Simon Blackburn). The paper is about the DLP instance: Given (g,h,n) to find integers 1 \leq a, b < n such that g^a = h^b, when n is much smaller than the order of g. This problem arises when one tries to trace transactions made using a proposed protocol by EMV (Mastercard/Visa) for card payments. (The standard attempts to make such transactions un-traceable in the sense that it is hard for an eavesdropper to "link" two different transactions made using the same card). The algorithmic content is to use the Gaudry-Schost algorithm for this problem, to get a low-storage algorithm that performs O( n ) group operations. The EMV standard proposed n=32, but this has been increased in response to the attack in this paper. Nevertheless, it is interesting that next-generation card payments will be protected by 256-bit elliptic curve cryptography.

Third talk of the session was "Constructing Abelian Surfaces for Cryptography via Rosenhain Invariants" by Kristin Lauter (joint work with Craig Costello, Alyson Deines-Schartz and Tonghai Yang). The paper is about constructing genus 2 curves using the CM method. Almost all previous work has used Igusa invariants and hence Mestre’s algorithm. The paper notes that using Rosenhain invariants is much simpler, and that the penalty that the class polynomials have higher degree is not necessarily a major problem in practice. Kristin also talked about how this method can give Kummer surface equations with relatively small constants, and expressed her philosophy that number theorists should be more engaged in applied subjects like cryptography, not only because the applications are important but also that these subjects can be a rich source of interesting theoretical questions.

Next was “Hyper-and-elliptic-curve cryptography” by Dan Bernstein. Dan, the sweet gentle soul that he is, gave an emotional appeal on behalf of a polar bear named “Fluffy” that we should try to use less energy by using more efficient crypto. This led to a discussion of Kummer surfaces and Edwards curves. The mathematical content was an explanation of a construction due to Scholten of genus 2 curves whose Jacobians are isogenous to the Weil restriction of Edwards curves. Dan explained how one can construct examples where the Kummer surface of the genus 2 Jacobian has an equation with small coefficients, and how one can efficiently pass between Edwards curve and Kummer surface representations of the same group. He was warmly thanked (globally) on behalf of Fluffy.

After lunch, Christophe Petit spoke about “Finding Roots in \mathbb{F}_{p^n} with the Successive Resultants Algorithm”. This is a new approach to factoring polynomials over finite fields of small characteristic. It does not provide a major speed-up for present applications, but is being suggested in the hope that it can lead to a new approach to finding solutions of a special form to multivariate polynomial equations.

Next Qi Cheng spoke on “Traps to the BGJT-Algorithm for Discrete Logarithms” (joint work with Daqing Wan and Jincheng Zhuang). The paper aims to reduce the number of heuristics in the quasi-polynomial-time algorithm for the DLP in finite fields of small characteristic. Note that there are several avenues to approach these isses, for example as discussed in Rob Granger’s talk at the Ascona DLP workshop.

Cecile Pierrot presented “The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields” (joint work with Razvan Barbulescu). This takes ideas of Coppersmith and Matyukhin for the number field sieve and applies them to a more general class of finite fields. These ideas lead to complexity improvements for the DLP in finite fields.

In the evening there was a poster session, followed by a “business meeting” that decided that ANTS 2016 should take place in (Bordeaux or Kaiserslautern) but failed to give a full solution to the problem.

The conference continues, but the talks are mainly on topics unrelated to elliptic curve cryptography. On Monday there will be a talk by David Kohel on the paper “On the quaternion l-isogeny path problem” with Kristin Lauter, Christophe Petit and Jean-Pierre Tignol. This paper is relevant to isogenies on supersingular elliptic curves and the Charles-Goren-Lauter hash function.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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