Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms

This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambe...

Full description

Saved in:
Bibliographic Details
Published in:ETRI journal 2005-10, Vol.27 (5), p.617-627
Main Authors: Park, Tae Jun, Lee, Mun‐Kyu, Park, Kunsoo, Chung, Kyo Il
Format: Article
Language:English
Subjects:
Frobenius expansion
Hyperelliptic curve
scalar multiplication
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambert‐Vanstone (GLV) endomorphisms. To compute kD for an integer k and a divisor D, we expand the integer k by the Frobenius endomorphism and the GLV endomorphism. We also present improved scalar multiplication algorithms that use the new expansion method. By our new expansion method, the number of divisor doublings in a scalar multiplication is reduced to a quarter, while the number of divisor additions is almost the same. Our experiments show that the overall throughputs of scalar multiplications are increased by 15.6 to 28.3 % over the previous algorithms when the algorithms are implemented over finite fields of odd characteristics.
ISSN:1225-6463
2233-7326
DOI:10.4218/etrij.05.0104.0171