Paper 2004/073

Index calculus for abelian varieties and the elliptic curve discrete logarithm problem

Pierrick Gaudry

Abstract

We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over $GF(q^3)$ in time $O(q^{10/7})$, with a reasonably small constant; and an elliptic problem over $GF(q^4)$ or a genus 2 problem over $GF(p^2)$ in time $O(q^{14/9})$ with a larger constant.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curvesWeil descentdiscrete logarithm problem
Contact author(s)
gaudry @ lix polytechnique fr
History
2004-03-04: received
Short URL
https://ia.cr/2004/073
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/073,
      author = {Pierrick Gaudry},
      title = {Index calculus for abelian varieties and the elliptic curve discrete logarithm problem},
      howpublished = {Cryptology ePrint Archive, Paper 2004/073},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/073}},
      url = {https://eprint.iacr.org/2004/073}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.