On index calculus algorithms for subfield curves

Steven D. Galbraith, Robert Granger, Simon-Philipp Merz, Christophe Petit

Research output: Chapter in Book/Report/Conference proceedingConference contribution

142 Downloads (Pure)


In this paper we further the study of index calculus methods for solving the elliptic curve discrete logarithm problem (ECDLP). We focus on the index calculus for subfield curves, also called Koblitz curves, defined over Fq with ECDLP in Fqn. Instead of accelerating the solution of polynomial systems during index calculus as was predominantly done in previous work, we define factor bases that are invariant under the q-power Frobenius automorphism of the field Fqn, reducing the number of polynomial systems that need to be solved. A reduction by a factor of 1/n is the best one could hope for. We show how to choose factor bases to achieve this, while simultaneously accelerating the linear algebra step of the index calculus method for Koblitz curves by a factor n2. Furthermore, we show how to use the Frobenius endomorphism to improve symmetry breaking for Koblitz curves. We provide constructions of factor bases with the desired properties, and we study their impact on the polynomial system solving costs experimentally.

Original languageEnglish
Title of host publicationSelected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers
EditorsOrr Dunkelman, Michael J. Jacobson, Jr., Colin O’Flynn
Number of pages24
ISBN (Electronic)9783030816520
ISBN (Print)9783030816513
Publication statusPublished - 21 Jul 2021
Event27th International Conference on Selected Areas in Cryptography, SAC 2020 - Virtual, Online
Duration: 21 Oct 202023 Oct 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Selected Areas in Cryptography, SAC 2020
CityVirtual, Online

Bibliographical note

Funding Information:
Acknowledgements. We thank Jean-Marc Couveignes and Reynald Lercier for their work on Galois invariant smoothness bases [2] and helpful conversations about the topic. Furthermore, we would like to thank the anonymous reviewers for their helpful comments on the submitted manuscript of this paper. Christophe Petit’s work was supported by EPSRC grant EP/S01361X/1. Simon-Philipp Merz was supported by the EPSRC grant EP/P009301/1.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On index calculus algorithms for subfield curves'. Together they form a unique fingerprint.

Cite this