F4 Traces and Index Calculus on Elliptic Curves Over Extension Fields

Recently, Gaudry and Diem have proposed an index calculus method for the resolution of the DLP on elliptic curves defined over extension fields. In this talk, I will first present a variant of this method that enables to decrease the asymptotic complexity of the DLP on E(Fqn) for a large range of q and n, then introduce a second improvement provided by the use of F4 traces for polynomial system solving. Finally, I will give a practical example of our index calculus variant to the oracle-assisted Static Diffie-Hellman Problem.

This is a joint work with Antoine Joux.

Date:
Speakers:
Vanessa Vitse
Affiliation:
Université de Versailles Saint-Quentin-en-Yvelines
    • Portrait of Jeff Running

      Jeff Running