Paper 2016/603

Koblitz curves over quadratic fields

Thomaz Oliveira, Julio López, Daniel Cervantes-Vázquez, and Francisco Rodríguez-Henríquez


In this work, we retake an old idea that Koblitz presented in his landmark paper, where he suggested the possibility of defining anomalous elliptic curves over the base field F4. We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. We also introduce two ordinary Koblitz-like elliptic curves defined over F4 that are equipped with efficient endomorphisms. To the best of our knowledge these endomorphisms have not been reported before. In order to achieve a fast reduction procedure, we adopted a redundant trinomial strategy that embeds elements of the field F4^m, with m a prime number, into a ring of higher order defined by an almost irreducible trinomial. We also present a number of techniques that allow us to take full advantage of the native vector instructions of high-end microprocessors. Our software library achieves the fastest timings reported for the computation of the timing-protected scalar multiplication on Koblitz curves, and competitive timings with respect to the speed records established recently in the computation of the scalar multiplication over binary and prime fields.

Available format(s)
Publication info
Preprint. MINOR revision.
koblitz curves software implementation
Contact author(s)
thomaz figueiredo @ gmail com
2017-11-21: last of 2 revisions
2016-06-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomaz Oliveira and Julio López and Daniel Cervantes-Vázquez and Francisco Rodríguez-Henríquez},
      title = {Koblitz curves over quadratic fields},
      howpublished = {Cryptology ePrint Archive, Paper 2016/603},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.