Cryptology ePrint Archive: Report 2016/603

Software implementation of Koblitz curves over quadratic fields

Thomaz Oliveira and Julio López 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 \F_4. We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. In order to achieve a fast reduction procedure, we adopted a redundant trinomial strategy that embeds elements of the field \F_{4^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 prime fields.

Category / Keywords: implementation / software implementation binary elliptic curves

Original Publication (with major differences): IACR-CHES-2016

Date: received 7 Jun 2016, last revised 10 Jun 2016

Contact author: thomaz figueiredo at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160610:170937 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]