Cryptology ePrint Archive: Report 2016/603

Koblitz curves over quadratic fields

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

Abstract: 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.

Category / Keywords: koblitz curves software implementation

Date: received 7 Jun 2016, last revised 21 Nov 2017

Contact author: thomaz figueiredo at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20171121:171545 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]