Cryptology ePrint Archive: Report 2006/204

Towards Minimizing Memory Requirement for Implementation of Hyperelliptic Curve Crytosystems

Pradeep Kumar Mishra and Pinakpani Pal and Palash Sarkar.

Abstract: Elliptic (ECC) and hyperelliptic curve cryptosystems (HECC) have emerged as cryptosystems of choice for small handheld and mobile devices. A lot of research has been devoted to the secure and efficient implementation on these devices. As such devices come with very low amount of resources, efficient memory management is an important issue in all such implementations. HECC arithmetic is now generally performed using so called explicit formulae. In literature, there is no result which focuses on the exact memory requirement for implementation these formulae. This is the first work to report such minimal memory requirement. Also, in the work we have provided a general methodology for realization of explicit formulae with minimal number of registers. Applying such methodology this work settles the issue for some important explicit formula available in the literature. This is an attempt to experimentally solve a particular instance based on HECC explicit formulae of the so called ``Register Sufficiency Problem", which is an NP-complete problem.

Category / Keywords: Elliptic and hyperelliptic curve cryptosystems, memory, explicit formula, divisor addition, divisor doubling, scalar multiplication.

Date: received 20 Jun 2006, last revised 20 Jun 2006

Contact author: pradeep at math ucalgary ca

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: There was some problem in the title of the paper in the earlier submission. Therefore this revision

Version: 20060621:052730 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]