New ways of finding relations in the Index Calculus for Jacobians of hyperelliptic curves
Speaker(s) : Alexandre WALLET (PolSys team, CNRS/INRIA/UPMC)
The families of Index-calculus algorithms are designed to solve the discrete logarithm problem (DLP) in abelian groups using as much as possible the underlying structures to accelerate the computations. This problem is used in several cryptographic protocols and thus, it is important to understand how to solve it to estimate its security.
Index-calculus algorithms have two phases. First, we collect relations and after there is a systematic linear algebra phase. Most of the recent work focuses on refining the harvesting of the relations. When we compute with the Jacobian of algebraic curves, the usual way of collecting a relation is to compute a divisor and then to test for its smoothness. This requires a good understanding of the arithmetic on such Jacobian varieties.
In this talk we will recall the usual polynomial representation of elements in Jacobians and we will present a new way of finding a relation in the Jacobian of hyperelliptic curves defined on finite field, minimizing the arithmetic cost and generalizing the ideas of Diem for small degree curves. We will also discuss the complexity depending on the genus of the hyperelliptic curve.
Joint work with Jean-Charles Faugère and Vanessa Vitse.
Elias.Tsigaridas (at) nulllip6.fr