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(N^1/2) group operations, where N is the size of the group (of prime order), as shown by Shoup [1]. 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(N^1/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(N^1/2) steps (group operations or arithmetic operations). The three main cases of interest are listed below.

Genus g &ge 3

For a hyperelliptic curve C over F_q with J(C) cyclic, the discrete logarithm program can be solved in soft-O(q^2-2/g) time [2]. This can be generalized to plane curves with J(C) of known structure, not necessarily cyclic [3].

Non-prime fields F_p^d

For a genus 2 curve C, the discrete logarithm problem in J(C/F_p^d) can be transferred to the Jacobian of a genus 4 curve over F_p when d = 2, and when d = 3 the problem can be transferred to a genus 6 curve [4] (other transfers are known for larger d and g). Once transferred to a higher genus curve, the discrete logarithm problem can be solved more efficiently using the result above.

Trace zero varieties

The discrete logarithm problem in the trace zero variety T₃(C) of a genus 2 curve C can be transferred to a genus 5 curve provided that #J₂(C) is divisible by 3. Otherwise, with high probability, the problem can transferred only to a curve of genus greater than 6 [4].

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

• For a genus 3 hyperelliptic curve over a prime field, m/n = 9/8.
  
  
• For a genus 2 curve over F_p² we have m/n = 4/3.
  
  
• For the trace zero variety of a genus 2 curve over F_p³ the ratio m/n is 5/4 when #J₂(C) is divisible by 3 and 6/5 otherwise.