Paper 2004/255

A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two

Izuru Kitamura, Masanobu Katagi, and Tsuyoshi Takagi

Abstract

We deal with a divisor class halving algorithm on hyperelliptic curve cryptosystems (HECC), which can be used for scalar multiplication, instead of a doubling algorithm. It is not obvious how to construct a halving algorithm, due to the complicated addition formula of hyperelliptic curves. In this paper, we propose the first halving algorithm used for HECC of genus 2, which is as efficient as the previously known doubling algorithm. From the explicit formula of the doubling algorithm, we can generate some equations whose common solutions contain the halved value. From these equations we derive four specific equations and show an algorithm that selects the proper halved value using two trace computations in the worst case. If a base point is fixed, we can reduce these extra field operations by using a pre-computed table which shows the correct halving divisor class —the improvement over the previously known fastest doubling algorithm is up to about 10%. This halving algorithm is applicable to DSA and DH scheme based on HECC. Finally, we present the divisor class halving algorithms for not only the most frequent case but also other exceptional cases.

Note: The old title of this paper was "A Point Halving Algorithm for Hyperellptic Curves".

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. This is a full version of ACISP 2005 paper.
Keywords
hyperelliptic curve cryptosystemsscalar multiplicationpoint halvingefficient computation
Contact author(s)
Izuru Kitamura @ jp sony com
History
2005-07-04: revised
2004-10-08: received
See all versions
Short URL
https://ia.cr/2004/255
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/255,
      author = {Izuru Kitamura and Masanobu Katagi and Tsuyoshi Takagi},
      title = {A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/255},
      year = {2004},
      url = {https://eprint.iacr.org/2004/255}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.