Paper 2020/1315

On Index Calculus Algorithms for Subfield Curves

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


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 $\mathbb{F}_q$ with ECDLP in $\mathbb{F}_{q^n}$. 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 $\mathbb{F}_{q^n}$, 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 $n^2$. 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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
elliptic curve discrete logarithmKoblitz curvessubfield curvesFrobenius endomorphism
Contact author(s)
s galbraith @ auckland ac nz
r granger @ surrey ac uk
simon-philipp merz 2018 @ rhul ac uk
christophe f petit @ gmail com
2020-10-23: received
Short URL
Creative Commons Attribution


      author = {Steven D.  Galbraith and Robert Granger and Simon-Philipp Merz and Christophe Petit},
      title = {On Index Calculus Algorithms for Subfield Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1315},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.