On Index Calculus Algorithms for Subfield Curves

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


Colleges, School and Institutes

External organisations

  • University of Auckland
  • University of Surrey
  • Royal Holloway University of London
  • Université Libre de Bruxelles


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. This work gives an answer to the problem raised in the literature on how the Frobenius endomorphism can be used to speed-up index calculus on subfield curves.


Original languageEnglish
Title of host publicationSelected Areas in Cryptography - SAC 2020
Publication statusAccepted/In press - 18 Sep 2020
EventSelected Areas in Cryptography - SAC 2020 - Virtual Event
Duration: 21 Oct 202023 Oct 2020

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceSelected Areas in Cryptography - SAC 2020
CityVirtual Event