Cryptographic applications based on the discrete logarithm problem require a cyclic group (or subgroup) with large prime order. The difficulty of computing discrete logarithms depends entirely on the representation of this group. If, for example, the group in question is represented as the additive integers mod p, then discrete logarithms can be computed quite easily even when p is very large (it suffices to find a multiplicative inverse mod p, easily accomplished with the Euclidean algorithm). On the other hand, if the "same" group is represented by the points of an elliptic curve or the Jacobian of a hyperelliptic curve, the discrete logarithm is believed to be very difficult to compute. Ideally, one would like a group to be represented generically so that it is effectively a black-box group, one in which the only means of obtaining information is by performing group operations and testing group elements for equality.
Under this idealized assumption, it can be proven that the discrete logarithm problem is hard, requiring &Omega(N1/2) group operations, where N is the size of the group (of prime order), as shown by Shoup . In practice this assumption is never realized. Any practical cryptographic system necessarily encodes information in the representation of group elements. For certain representations, including many Jacobians, it is believed that this information does not make the discrete logarithm problem any easier and that a &Omega(N1/2) lower bound applies. There is not, and almost certainly never will be, any proof that this belief is justified. It is a working assumption and should be regarded as such.
In several cases this assumption is actually known to be false, i.e., there are algorithms which can compute the discrete logarithm in certain Jacobians using o(N1/2) steps (group operations or arithmetic operations). The three main cases of interest are listed below.
Note that for fixed g and d, these algorithms still require exponential time, O(exp(clogN)), but the constant c is less than 1/2.
We take as our "gold standard" a genus 2 Jacobian over a prime field with prime order N, which is unaffected by the results above. To assess the
"effective" security of any particular Jacobian (or trace zero variety), we determine how much larger the group would need to be to make the difficulty of the
discrete logarithm problem roughly equivalent, using currently known algorithms. If n = lgN is the size of our standard genus 2 Jacobian and m=lgM
is the size of the group in question, we are interested in the ratio m/n. Applying the results above, we then have