Public-key Cryptography: Theory and Practice

**4.6. The Hyperelliptic Curve Discrete Logarithm Problem

The hyperelliptic curve discrete logarithm problem (HECDLP) has attracted less research attention than the ECDLP. Surprisingly, however, there exist subexponential (index calculus) algorithms for solving the HECDLP over curves of large genus. Adleman, DeMarrais and Huang first proposed such an algorithm [2] (which we will refer to as the ADH algorithm). Enge [86] suggested some modifications of the ADH algorithm and provided rigorous analysis of its running time. Gaudry [105] simplified the ADH algorithm and even implemented it. Gaudry’s experimentation suggests that it is feasible to compute discrete logarithms in Jacobians of almost cryptographic sizes, given that the genus of the underlying ...