Fast Scalar Multiplication Algorithms On Hyperelliptic Curves

Hyperelliptic curves are a special class of algebraic curves, and generally regarded as generalizations of elliptic curves. Public-key cryptography applying hyperelliptic curves has many advantages compared to others. For example, comparing with elliptic curve cryptosystem, it can provide the same level of security with smaller base field and shorter operand. And there are far more alternative curves as the genus increases over the same definition field. So the advent of hyperelliptic curve cryptosystem (HECC) provides a good choice for constructing a secure cryptosystem. And it has also received tremendous attentions and researches. However, the hyperelliptic curve discrete logarithm problem which HECC is based on is constructed on an abelian group named Jacobian. It is much more complex than the elliptic curve rational point group so that HECC has a slower implementation and its application hasn’t become so widespread yet.One of the most important and also most time-consuming operations in the implementation of HECC is the divisor scalar multiplication. So speeding up scalar multiplications is critical to the practicality of HECC.This paper focuses on the hyperelliptic curve over binary fields. The work and results mainly include the following aspects.(1) In Chapter1, we first introduce the research status and the critical problems on HECC. Then the existing methods to speed up the scalar multiplications on HECC are summarized. These methods include:optimizing the group operations on the Jacobian, using divisor class halving algorithm instead of doubling, using the addition and doubling algorithms of degenerate divisors, parallelizing the explicit formulae for arithmetic on the Jacobian, by appropriately coding the scalars, and by selecting the special curves.(2) In Chapter3, we propose the sketch of the divisor class halving algorithm for the most frequent case for genus-3hyperelliptic curve over binary fields. The sketch for the general curve shows that the computation amount of the halving algorithm is closely related to the parameters of the curve equation. So we focus on a class of curve Ce0:y2+h0y=x7+f3x3+f1x+f0(h0≠0). We give the complete procedures of divisor halving on Ce0and also their explicit formulae which prove to be more efficient than the previously known best doubling algorithm. For the most frequent case, the halving algorithm saves one multiplication and two squarings in finite fields compared to the best doubling algorithm.(3) In Chapter4, two fast algorithms are proposed to compute the scalar multiplications on a class of genus-2hyperelliptic curve Cab:y2+y=x5+ax+b over binary fields. Making use of the idea of simple divisor, we derive an efficient formula to directly obtain the computing result of4rD where r is a positive integer and D is an element in the Jacobian group. By expressing thescalar in4-ary representation, two efficient scalar multiplication algorithms are developed based onthe formula. Compared with the binary method, the two algorithms can respectively cost45.5%and53.1%less field operations without using pre-computation technique. Combining withpre-computation technique, the two data turns into56.1%and53.2%, respectively.(4) In Chapter5, we deal with the characteristic polynomials of the curveC abover binaryfield2n, wherea,b2nand n is an arbitrary positive integer. We first introduce all therepresentatives of isomorphism classes of the curveC ab. Then we respectively discuss thecharacteristic polynomial of each class. Finally we determine the characteristic polynomial of thecurveC abfor the situation when n1mod2, n2mod4andn0mod4, Tr4(a)0. Whenn0mod4andTr4(a)0, we just give all four possible formulae of the characteristicpolynomials. And usig these obtained formulae, we also give a fast algorithm to compute the divisorscalar multiplications on the curveC ab. It’s much more efficient than (signed) binary method.