Paper 2004/073 Original: eprint.iacr.org/2004/073 ↗
Index calculus for abelian varieties and the elliptic curve discrete logarithm problem
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)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2004-03-04: last updated
- 2004-03-04: published
- Short URL
- https://ia.cr/2004/073
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2004/073}
}