Cover and Decomposition Index Calculus on Elliptic Curves made practical. Application to a seemingly secure curve over $\F_{p^6}$

Antoine Joux; Vanessa Vitse

Paper 2011/020 Original: eprint.iacr.org/2011/020 ↗

Cover and Decomposition Index Calculus on Elliptic Curves made practical. Application to a seemingly secure curve over $\F_{p^6}$

Antoine Joux

Vanessa Vitse

Abstract

We present a new variant of cover and decomposition attacks on the elliptic curve discrete logarithm problem, that combines Weil descent and decomposition-based index calculus into a single discrete logarithm algorithm. This variant applies, at least theoretically, to all composite degree extension fields, and is particularly well-suited for curves defined over $\F_{p^6}$. We give a real-size example of discrete logarithm computations on a seemingly secure curve defined over a 130$-bit degree $6$ extension field.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2012-01-30: last updated; 2011-01-14: published
Short URL: https://ia.cr/2011/020
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2011/020,
      author = {Antoine Joux and Vanessa Vitse},
      title = {Cover and Decomposition Index Calculus on Elliptic Curves made practical. Application to a seemingly secure curve over $\F_{p^6}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/020},
      year = {2011},
      url = {https://eprint.iacr.org/2011/020}
}