Cantor versus Harley: Optimization and Analysis of Explicit Formulae for Hyperelliptic Curve Cryptosystem

Thomas Wollinger, Jan Pelzl, Chris­tof Paar

IEEE Transactions on Computers, Vol. 54, No. 7, pp. 861-872, July 2005.


Abstract

Hyperelliptic curves (HEC) look promising for cryptographic applications, because of their short operand size compared to other public-key schemes. The operand sizes seem well suited for small processor architectures, where memory and speed are constrained. However, the group operation has been believed to be too complex and thus, HEC have not been used in this context so far. In recent years, a lot of effort has been made to speed up group operation of genus-2 HEC. In this contribution, we increase the efficiency of the genus-2, genus-3, and genus-4 hyperelliptic curve cryptosystem (HECC). For certain genus-3 curves we can gain almost 80% performance for a group doubling. This work not only improves Harley’s algorithm, but also improves the original algorithm introduced by Cantor. Contrary to common belief, we show that it is also practical for certain curves to use Cantor’s algorithm to obtain the highest efficiency for the group operation. In addition, we introduce a general reduction method for polynomials according to Karatsuba. We implemented the most efficient group operations on Pentium and ARM microprocessors.

[pdf] [zip]

Tags: ieee