A general framework for subexponential discrete logarithm algorithms (Q2781453)

A large family of cryptographic systems is based on the difficulty of the discrete logarithm problem: Given a group \(G\) and some element \(a\in G\) and \(b\) such that \(b \in \langle a\rangle\) find an integer \(n\) with \(a^n = b\). Groups used for this purpose include the multiplicative group of finite fields, the class group of number fields (mostly imaginary quadratic fields) and divisor class groups of elliptic and hyperelliptic curves.NEWLINENEWLINENEWLINEOver the last few years a variety of subexponential methods have been developed for these groups to solve the discrete logarithm problem. In this article the authors present a generic framework that, under the additional assumption that the order of \(a\) is known, will find \(n\) in all the above cases. Futhermore, specializations of their framework yield the previously known best algorithms or improve them. In the case of Jacobians of hyperelliptic curves over finite fields, the new methods give a substantial improvement over previously known algorithms.NEWLINENEWLINENEWLINEThe power of their generic approach is also demonstrated by a rigorous complexity analysis showing that under the assumption of the order of \(a\) being known, the discrete logarithm problem is solvable in expected subexponential time. A key ingredient is a randomized version of Lanczos' algorithm, for which they give a complexity analysis too.