Speeding up the scalar multiplication in the Jacobians of hyperelliptic curves using Frobenius map

Abstract

In [8] Koblitz suggested to make use of a Frobenius expansion to speed up the scalar multiplications in the Jacobians of hyperelliptic curves over the characteristic 2 field. Recently, Gunther et. al. [6] have modified Koblitz's Frobenius expansion method and applied it to the Koblitz curves of genus 2 over F-2 to speed up the scalar multiplication. In this paper, we show that the method given in [6] can be extended to the case when the hyperelliptic curves are defined over the finite field of any characteristic. For cryptographic purposes, we restrict our interest only to those with genus 2,3,4. We give a theoretical efficiency of our method by comparing to the double-and-add method over the Jacobians. As a result, with some reference tables we can reduce the cost of double-and-add method to nearly 41%.