Paper 2011/098

Computing Discrete Logarithms in the Jacobian of High-Genus Hyperelliptic Curves over Even Characteristic Finite Fields

M. D. Velichka, M. J. Jacobson Jr., and A. Stein

Abstract

We describe improved versions of index-calculus algorithms for solving discrete logarithm problems in Jacobians of high-genus hyperelliptic curves defined over even characteristic fields. Our first improvement is to incorporate several ideas for the low-genus case by Gaudry and Theriault, including the large prime variant and using a smaller factor base, into the large-genus algorithm of Enge and Gaudry. We extend the analysis in [24] to our new algorithm, allowing us to predict accurately the number of random walk steps required to find all relations, and to select optimal degree bounds for the factor base. Our second improvement is the adaptation of sieving techniques from Flassenberg and Paulus, and Jacobson to our setting. The new algorithms are applied to concrete problem instances arising from the Weil descent attack methodology for solving the elliptic curve discrete logarithm problem, demonstrating significant improvements in practice.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Submitted to Mathematics of Computation
Keywords
hyperelliptic curvesdiscrete logarithm problemsievingWeil descent
Contact author(s)
jacobs @ cpsc ucalgary ca
History
2011-02-28: received
Short URL
https://ia.cr/2011/098
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/098,
      author = {M.  D.  Velichka and M.  J.  Jacobson Jr. and A.  Stein},
      title = {Computing Discrete Logarithms in the Jacobian of High-Genus Hyperelliptic Curves over Even Characteristic Finite Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2011/098},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/098}},
      url = {https://eprint.iacr.org/2011/098}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.