**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 curve is high (say ≥ 6). Enge and Gaudry [87] proved rigorously that as long as the genus g is greater than ln q ( being the field over which the curve is defined), the ADH algorithm (and its improvements) run in time L(q^g, 1/2, ).

In what follows, we outline Gaudry’s version of the ADH algorithm and refer to this as the ADH–Gaudry algorithm. Let C : Y² + u(X)Y = v(X) be a hyperelliptic curve of genus g defined over a finite field . We assume that the cardinality of the Jacobian is known and has a suitably large prime divisor m. We assume further that a reduced divisor of order m is available, and we want to compute the discrete logarithm ind_α β of with respect to α.

4.6.1. Choosing the Factor Base

Recall that every reduced divisor can be written uniquely as , l ≤ g, where for i ≠ j the points P_i and P_j are not opposite of each other. Only ordinary points (not special points) may appear more than once in the list P₁, . . . , P_l. We also know that such a divisor can be represented by a pair of unique polynomials a, satisfying deg b < deg a ≤ g and a|(b² + bu – v). In that case, we write D = Div(a, b). What interests us is the fact that the roots of the polynomial a are precisely the X-coordinates of the points P₁, . . . , P_l. This fact leads to the very useful concepts of prime divisors and smooth divisors.

Definition 4.4.

In order to set up a factor base B, we predetermine a smoothness bound δ and let B consist of all the prime divisors with deg a ≤ δ. For simplicity, we take δ = 1. This is indeed a practical choice, when the genus g is not too large (say, g ≤ 9). Let be an (irreducible) polynomial of degree 1. In order to find out such that Div(a, b) is a prime divisor, we first see that deg b < deg a, that is, . Furthermore, a|(b² + bu – v): that is, b² + bu – v ≡ 0 (mod X – h); that is, b² + bu(h) – v(h) = 0. Thus, the desired values of , if existent, can be found by solving a quadratic equation over . There are q irreducible polynomials of degree 1 and for each such a there are either two or no solutions for . Assuming that both these possibilities are equally likely, we conclude that the size of the factor base is ≈ q.

4.6.2. Checking the Smoothness of a Divisor

In order to check for the smoothness of a divisor over the factor base B, we first factor a over . Under the assumption that δ = 1, the divisor D is smooth if and only if a splits completely over . Let us write a(X) = (X –h₁) ··· (X –h_l), . Then for some we have , where D_i := Div(X – h_i, k_i). We may use trial divisions (that is, trial subtractions in this additive setting) by elements of B in order to determine the prime divisors D₁, . . . , D_l of D. Proposition 4.5 establishes the probability that a randomly chosen element of is smooth.

Proposition 4.5.

4.6.3. The Algorithm

Now, we have all the machinery required to describe the basic version of the index calculus method for computing ind_α β in . In the first stage, we choose a random and compute the (reduced) divisor jα and check if jα is smooth over the factor base B. Every smooth jα gives a relation: that is, a linear congruence modulo m involving the (unknown) indices of the elements of B to the base α. After sufficiently many (say, ≥ 2(#B)) such relations are found, the system of linear congruences collected is expected to be of full rank and is solved modulo m. This gives us the indices of the elements of the factor base. Each congruence collected above contains at most g non-zero coefficients and so the system is necessarily sparse. In the second stage, we find out a single random j for which β +jα is smooth. The database prepared in the first stage then immediately gives ind_α β.

The Hasse–Weil Bounds (3.8) on p 226 show that the cardinality of is approximately q^g. Thus O(g log q) bits are needed to represent an element of . This fact is consistent with the representation of reduced divisors by pairs of polynomials. Gaudry [105] calculates that this variant of the ICM does O(q² + g!q) operations, each of which takes polynomial time in the input size g log q. If g is considered to be constant, the running time becomes O(q² log^t q) (that is, O^~(q²)) for some real t > 0. A square root method on runs in (expected) time O^~(q^g/2). Thus for g > 4 the index calculus method performs better than the square root methods. Indeed Gaudry’s implementation of this algorithm is capable of computing in a few days discrete logs in the curve of genus 6 mentioned above. The Jacobian of this curve is of cardinality ≈ 10⁴⁰.

For cryptographic purposes, we should have . If we want to take q small (so that multi-precision arithmetic can be avoided), we should choose large values of g. But this choice makes the ADH–Gaudry algorithm quite efficient. For achieving the desired level of security in cryptographic applications, hyperelliptic curves of genus 2, 3 and 4 only are recommended.