Generating Secure Genus Two Hyperelliptic Curves Using Elkies' Point Counting Algorithm

Naoki KANAYAMA  Koh-ichi NAGAO  Shigenori UCHIYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.4   pp.919-927
Publication Date: 2003/04/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
Keyword: 
hyperelliptic curve,  BSGS,  point counting,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper proposes an improvement of Elkies' point counting algorithm for the Jacobian of a genus 2 hyperelliptic curve defined over a finite field in a practical sense and introduces experimental results. Our experimental results show that we can generate a cryptographic secure genus 2 hyperelliptic curve, where the order of its Jacobian is a 160-bit prime number in about 8.1 minutes on average, on a 700 MHz PentiumIII level PC. We improve Elkies' algorithm by proposing some complementary techniques for speeding up the baby-step giant-step.