Paper 2003/203

Novel Efficient Implementations of Hyperelliptic Curve Cryptosystems using Degenerate Divisors

Masanobu Katagi, Izuru Kitamura, Toru Akishita, and Tsuyoshi Takagi

Abstract

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC). However, it is expected that HECC still can be improved due to their mathematically rich structure. We consider here the application of degenerate divisors of HECC to scalar multiplication. We investigate the operations of the degenerate divisors in the Harley algorithm and the Cantor algorithm of genus 2. The timings of these operations are reported. We then present a novel efficient scalar multiplication method using the degenerate divisors. This method is applicable to cryptosystems with fixed base point, e.g., ElGamal-type encryption, sender of Diffie-Hellman, and DSA. Using a Xeon processor, we found that the double-and-add-always method using the degenerate base point can achieve about a 20% increase in speed for a 160-bit HECC. However, we mounted an timing attack using the time difference to designate the degenerate divisors. The attack assumes that the secret key is fixed and the base point can be freely chosen by the attacker. Therefore, the attack is applicable to ElGamal-type decryption and single-pass Diffie-Hellman — SSL using a hyperelliptic curve could be vulnerable to the proposed attack. Our experimental results show that one bit of the secret key for a 160-bit HECC can be recovered by calling the decryption oracle 500 times.

Note: The old title of this paper was "A Timing Attack on Hyperelliptic Curve Cryptosystems".

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. This is a full version of WISA 2004 paper.
Keywords
hyperelliptic curve cryptosystemscalar multiplicationtiming attackdegenerate divisorefficient computation
Contact author(s)
Masanobu Katagi @ jp sony com
History
2004-08-13: last of 6 revisions
2003-09-26: received
See all versions
Short URL
https://ia.cr/2003/203
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/203,
      author = {Masanobu Katagi and Izuru Kitamura and Toru Akishita and Tsuyoshi Takagi},
      title = {Novel Efficient Implementations of Hyperelliptic Curve Cryptosystems using Degenerate Divisors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2003/203},
      year = {2003},
      url = {https://eprint.iacr.org/2003/203}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.