Paper 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.