Advances in Mathematics of Communications (AMC)

Index calculus in the trace zero variety

Pages: 515 - 539, Volume 9, Issue 4, November 2015      doi:10.3934/amc.2015.9.515

       Abstract        References        Full Text (555.0K)       Related Articles       

Elisa Gorla - Institut de Mathématiques, Université de Neuchâtel, Rue Emile-Argand 11, 2000 Neuchâtel, Switzerland (email)
Maike Massierer - Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland (email)

Abstract: We discuss how to apply Gaudry's index calculus algorithm for abelian varieties to solve the discrete logarithm problem in the trace zero variety of an elliptic curve. We treat in particular the practically relevant cases of field extensions of degree 3 or 5. Our theoretical analysis is compared to other algorithms present in the literature, and is complemented by results from a prototype implementation.

Keywords:  Elliptic curve cryptography, discrete logarithm problem, index calculus, trace zero variety.
Mathematics Subject Classification:  Primary: 14G50, 11G25, 11Y40; Secondary: 11T71, 14K15, 14H52.

Received: April 2014;      Available Online: November 2015.