F4 Traces and Index Calculus on Elliptic Curves Over Extension Fields

Date

October 20, 2010

Speaker

Vanessa Vitse

Affiliation

Université de Versailles Saint-Quentin-en-Yvelines

Overview

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.

‚Äč