Cover and Decomposition Index Calculus on Elliptic Curve

Explore the discrete logarithm problem on elliptic curves in this Eurocrypt 2012 conference talk. Delve into the index calculus methods and their application to elliptic curve cryptography. Learn about the transfer of the Elliptic Curve Discrete Logarithm Problem (ECDLP) via cover maps, including the GHS construction and decomposition attacks. Examine Nagao's approach for decompositions and its analysis, followed by a discussion on modified index calculus. Investigate a special case involving quadratic extensions in odd characteristics and the sieving technique. Discover the combined attack and its application to the sextic extension case. Conclude with a concrete attack demonstration on a 150-bit curve and explore scaling data for implementation.

Intro
The discrete logarithm problem on elliptic curve Use the group of points of an elliptic curve defined over a finite field
Basic outline of index calculus methods
Transfer of the ECDLP via cover maps Weil de
The GHS construction
Decomposition attack
Nagao's approach for decompositions
Analysis of Nagao's approach
Modified index calculus
A special case: quadratic extensions in odd char
The sieving technique Fact: solutions of the polynomial system only give the polynomial
Second ingredient: the combined attack
The sextic extension case
A concrete attack on a 150-bit curve
Scaling data for our implementation