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

Masaki GONDA; Kazuto MATSUO; Kazumaro AOKI; Jinhui CHAO; Shigeo TSUJII

doi:10.1093/ietfec/e88-a.1.89

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

Masaki GONDA, Kazuto MATSUO, Kazumaro AOKI, Jinhui CHAO, Shigeo TSUJII

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.1 pp.89-96

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.1.89

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Public Key Cryptography

Cite this

Copy

Masaki GONDA, Kazuto MATSUO, Kazumaro AOKI, Jinhui CHAO, Shigeo TSUJII, "Improvements of Addition Algorithm on Genus 3 Hyperelliptic Curves and Their Implementation" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 1, pp. 89-96, January 2005, doi: 10.1093/ietfec/e88-a.1.89.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.1.89/_p

Copy

@ARTICLE{e88-a_1_89,
author={Masaki GONDA, Kazuto MATSUO, Kazumaro AOKI, Jinhui CHAO, Shigeo TSUJII, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improvements of Addition Algorithm on Genus 3 Hyperelliptic Curves and Their Implementation},
year={2005},
volume={E88-A},
number={1},
pages={89-96},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e88-a.1.89},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Improvements of Addition Algorithm on Genus 3 Hyperelliptic Curves and Their Implementation
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 89
EP - 96
AU - Masaki GONDA
AU - Kazuto MATSUO
AU - Kazumaro AOKI
AU - Jinhui CHAO
AU - Shigeo TSUJII
PY - 2005
DO - 10.1093/ietfec/e88-a.1.89
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2005
AB - 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.
ER -