The point decomposition problem over hyperelliptic curves: Toward efficient computation of discrete logarithms in even characteristic

Computing discrete logarithms is generically a difficult problem. For divisor class groups of curves defined over extension fields, a variant of the Index-Calculus called decomposition attack is used, and it can be faster than generic approaches. In this situation, collecting the relations is done by solving multiple instances of the point m-decomposition problem (PDP_m). An instance of this problem can be modelled as a zero-dimensional polynomial system. Solving is done with Gröbner bases algorithms, where the number of solutions of the system is a good indicator for the time complexity of the solving process. For systems arising from a PDP_m context, this number grows exponentially fast with the extension degree. To achieve an efficient harvesting, this number must be reduced as much as possible. Extending the elliptic case, we introduce a notion of summation ideals to describe PDP_m instances over higher genus curves, and compare to Nagao’s general approach to PDP_m solving. In even characteristic we obtain reductions of the number of solutions for both approaches, depending on the curve’s equation. In the best cases, for a hyperelliptic curve of genus g, we can divide the number of solutions by 2 ^{( n - 1 ) ( g + 1 )}. For instance, for a type II genus 2 curve defined over F293 whose divisor class group has cardinality a near-prime 184 bits integer, the number of solutions is reduced from 4096 to 64. This is enough to build the matrix of relations in around 7 days with 8000 cores using a dedicated implementation.