On the discrete logarithm problem in class groups of curves

Abstract:

We study the discrete logarithm problem in degree 0 class groups of curves over finite fields, with particular emphasis on curves of small genus. We prove that for every fixed $g \geq 2$, the discrete logarithm problem in degree 0 class groups of curves of genus $g$ can be solved in an expected time of $\tilde {\mathcal {O}}(q^{2 - \frac {2}{g}})$, where $\mathbb {F}_q$ is the ground field. This result generalizes a corresponding result for hyperelliptic curves given in imaginary quadratic representation with cyclic degree 0 class group, and just as this previous result, it is obtained via an index calculus algorithm with double large prime variation.

Generalizing this result, we prove that for fixed $g_0 \geq 2$ the discrete logarithm problem in class groups of all curves $\mathcal {C}/\mathbb {F}_q$ of genus $g \geq g_0$ can be solved in an expected time of $\tilde {\mathcal {O}}((q^{g})^{\frac {2}{g_0} (1 - \frac {1}{g_0})})$ and in an expected time of $\tilde {\mathcal {O}}(\# \mathrm {Cl}^0(\mathcal {C})^{\frac {2}{g_0} (1 - \frac {1}{g_0})})$.

As a complementary result we prove that for any fixed $n \in \mathbb {N}$ with $n \geq 2$ the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields $\mathbb {F}_{q^n}$, $q$ a prime power, can be solved in an expected time of $\tilde {\mathcal {O}}(q^{2 - \frac {2}{n}})$.

Furthermore, we give an algorithm for the efficient construction of a uniformly randomly distributed effective divisor of a specific degree, given the curve and its $L$-polynomial.