Paper 2009/157

Efficient Halving for Genus 3 Curves over Binary Fields

Peter Birkner and Nicolas Thériault

Abstract

In this article, we deal with fast arithmetic in the Picard group of hyperelliptic curves of genus 3 over binary fields. We investigate both the optimal performance curves, where $h(x)=1$, and the more general curves where the degree of $h(x)$ is 1, 2 or 3. For the optimal performance curves, we provide explicit halving and doubling formulas; not only for the most frequent case but also for all possible special cases that may occur when performing arithmetic on the proposed curves. In this situation, we show that halving offers equivalent performance to that of doubling when computing scalar multiples (by means of an halve-and-add algorithm) in the divisor class group. For the other types of curves where halving may give performance gains (when the group order is twice an odd number), we give explicit halving formulas which outperform the corresponding doubling formulas by about 10 to 20 field multiplications per halving. These savings more than justify the use of halvings for these curves, making them significantly more efficient than previously thought. For halving on genus 3 curves there is no previous work published so far.

Note: This is the extended version of the paper including more curve types and halving formulas.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Extended version
Keywords
hyperelliptic curvegenus 3divisor classhalvingdoubling
Contact author(s)
p birkner @ tue nl
History
2009-04-22: revised
2009-04-07: received
See all versions
Short URL
https://ia.cr/2009/157
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/157,
      author = {Peter Birkner and Nicolas Thériault},
      title = {Efficient Halving for Genus 3 Curves over Binary Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2009/157},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/157}},
      url = {https://eprint.iacr.org/2009/157}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.