Cryptology ePrint Archive: Report 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.

Category / Keywords: elliptic curve, discrete logarithm, index calculus, Weil descent, decomposition attack

Date: received 11 Jan 2011, last revised 30 Jan 2012

Contact author: vanessa vitse at prism uvsq fr

Available formats: PDF | BibTeX Citation

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

Version: 20120130:161235 (All versions of this report)

Discussion forum: Show discussion | Start new discussion