Improvements of Addition Algorithm on Genus 3 Hyperelliptic Curves and Their Implementation

Masaki GONDA  Kazuto MATSUO  Kazumaro AOKI  Jinhui CHAO  Shigeo TSUJII  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.1   pp.89-96
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.1.89
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Cryptography
genus 3 hyperelliptic curves,  hyperelliptic curve cryptosystems,  addition algorithm,  Cantor algorithm,  Harley algorithm,  Toom's multiplication,  

Full Text: PDF(225.6KB)>>
Buy this Article

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.