Paper 2011/020

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

Antoine Joux and 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.

Note: Extended version of the accepted paper at Eurocrypt 2012.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curvediscrete logarithmindex calculusWeil descentdecomposition attack
Contact author(s)
vanessa vitse @ prism uvsq fr
History
2012-01-30: last of 3 revisions
2011-01-14: received
See all versions
Short URL
https://ia.cr/2011/020
License
Creative Commons Attribution
CC BY

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},
      note = {\url{https://eprint.iacr.org/2011/020}},
      url = {https://eprint.iacr.org/2011/020}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.