Cryptology ePrint Archive: Report 2008/194

Endomorphisms for faster elliptic curve cryptography on a large class of curves

Steven D. Galbraith and Xibin Lin and Michael Scott

Abstract: Efficiently computable homomorphisms allow elliptic curve point multiplication to be accelerated using the Gallant-Lambert-Vanstone (GLV) method. We extend results of Iijima, Matsuo, Chao and Tsujii which give such homomorphisms for a large class of elliptic curves by working over quadratic extensions and demonstrate that these results can be applied to the GLV method.

Our implementation runs in between 0.70 and 0.84 the time of the previous best methods for elliptic curve point multiplication on curves without small class number complex multiplication. Further speedups are possible when using more special curves.

Category / Keywords: public-key cryptography / elliptic curves, point multiplication, GLV method, Isogenies

Publication Info: Eurocrypt 2009

Date: received 2 May 2008, last revised 29 Oct 2009

Contact author: mike at computing dcu ie

Available formats: PDF | BibTeX Citation

Note: Full Version of Eurocrypt 2009 paper

Version: 20091029:134939 (All versions of this report)

Discussion forum: Show discussion | Start new discussion