Scalar multiplication methods using the Frobenius maps are known for efficient methods to speed up (hyper)elliptic curve cryptosystems. However, those methods are not efficient for the cryptosystems constructed on fields of small extension degrees due to costs of the field operations. Iijima et al. showed that one can use certain automorphisms on the quadratic twists of elliptic curves for fast scalar multiplications without the drawback of the Frobenius maps. This paper shows an extension of the automorphisms on the Jacobians of hyperelliptic curves of arbitrary genus.

This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a Cab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the Cab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC). Concerning the security of HECC, the theta divisors play an important role. The scalar multiplication using a random base point is vulnerable to an exceptional procedure attack, which is a kind of side-channel attacks, using theta divisors. In the case of cryptographic protocols of the scalar multiplication using fixed base point, however, the exceptional procedure attack is not applicable. First, we present novel efficient scalar multiplication using theta divisors, which is the positive application of theta divisors on HECC. Second, we develop a window-based method using theta divisors that is secure against side-channel attacks. It is not obvious how to construct a base point D such that all pre-computed points are theta divisors. We present an explicit algorithm for generating such divisors.

Genus 3 hyperelliptic curve cryptosystems are capable of fast-encryption on a 64-bit CPU, because a 56-bit field is enough for their definition fields. Recently, Kuroki et al. proposed an extension of the Harley algorithm, which had been known as the fastest addition algorithm of divisor classes on genus 2 hyperelliptic curves, on genus 3 hyperelliptic curves and Pelzl et al. improved the algorithm. This paper shows an improvement of the Harley algorithm on genus 3 hyperelliptic curves using Toom's multiplication. The proposed algorithm takes only I + 70M for an addition and I + 71M for a doubling instead of I + 76M and I + 74M respectively, which are the best possible of the previous works, where I and M denote the required time for an inversion and a multiplication over the definition field respectively. This paper also shows 2 variations of the proposed algorithm in order to adapt the algorithm to various platforms. Moreover this paper discusses finite field arithmetic suitable for genus 3 hyperelliptic curve cryptosystems and shows implementation results of the proposed algorithms on a 64-bit CPU. The implementation results show a 160-bit scalar multiplication can be done within 172 µs on a 64-bit CPU Alpha EV68 1.25 GHz.

Counting the number of points of Jacobian varieties of hyperelliptic curves over finite fields is necessary for construction of hyperelliptic curve cryptosystems. Recently Gaudry and Harley proposed a practical scheme for point counting of hyperelliptic curves. Their scheme consists of two parts: firstly to compute the residue modulo a positive integer m of the order of a given Jacobian variety, and then search for the order by a square-root algorithm. In particular, the parallelized Pollard's lambda-method was used as the square-root algorithm, which took 50CPU days to compute an order of 127 bits. This paper shows a new variation of the baby step giant step algorithm to improve the square-root algorithm part in the Gaudry-Harley scheme. With knowledge of the residue modulo m of the characteristic polynomial of the Frobenius endomorphism of a Jacobian variety, the proposed algorithm provides a speed up by a factor m, instead of in square-root algorithms. Moreover, implementation results of the proposed algorithm is presented including a 135-bit prime order computed about 15 hours on Alpha 21264/667 MHz and a 160-bit order.

We consider the performance of hyperelliptic curve cryptosystems over the fields Fp vs. F2n. We analyze the complexity of the group law of the jacobians JC(Fp) and JC(F2n) and compare their performance taking into consideration the effectiveness of the word size (32-bit or 64-bit) of the applied CPU (Alpha and Pentium) on the arithmetic of the definition field. Our experimental results show that JC(F2n) is faster than JC(Fp) on an Alpha, whereas JC(Fp) is faster than JC(F2n) on a Pentium. Moreover, we investigate the algorithm of the jacobian and the definition-field arithmetic to clarify our results from a practical point of view, with theoretical analysis.