Parallel Formulations of Scalar Multiplication on Koblitz Curves

Omran Ahmadi (University of Waterloo, Canada)

Darrel Hankerson (Auburn University, USA)

Francisco Rodríguez-Henríquez (CINVESTAV-IPN, Mexico)

Abstract: We present an algorithm that by using the τ and τ^-1 Frobenius operators concurrently allows us to obtain a parallelized version of the classical τ-and-add scalar multiplicationalgorithm for Koblitz elliptic curves. Furthermore, we report suitable irreducible polynomials that lead to efficient implementations of both τ and τ^-1, thus showing that our algorithm canbe effectively applied on all the NIST-recommended curves. We also present design details of software and hardware implementations of our procedure. In a two-processor workstation soft-ware implementation, we report experimental data showing that our parallel algorithm is able to achieve a speedup factor of almost 2 when compared with the standard sequential point multipli-cation. In our hardware implementation, the parallel version yields a more modest acceleration of 17% when compared with the traditional point multiplication algorithm. Although the focus ison Koblitz curves, analogous strategies are discussed for other curves, in particular for random curves over binary fields.

Keywords: Koblitz curves, elliptic curve cryptography, fast cryptographic algorithms, finite field arithmetic

Categories: B.2.4, E.3