
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Improvements of Addition Algorithm on Genus 3 Hyperelliptic Curves and Their Implementation
Masaki GONDA Kazuto MATSUO Kazumaro AOKI Jinhui CHAO Shigeo TSUJII
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E88A
No.1
pp.8996 Publication Date: 2005/01/01 Online ISSN:
DOI: 10.1093/ietfec/e88a.1.89 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Public Key Cryptography Keyword: genus 3 hyperelliptic curves, hyperelliptic curve cryptosystems, addition algorithm, Cantor algorithm, Harley algorithm, Toom's multiplication,
Full Text: PDF(225.6KB)>>
Summary:
Genus 3 hyperelliptic curve cryptosystems are capable of fastencryption on a 64bit CPU, because a 56bit 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 64bit CPU. The implementation results show a 160bit scalar multiplication can be done within 172 µs on a 64bit CPU Alpha EV68 1.25 GHz.

