### Implementing 4-Dimensional GLV Method on GLS Elliptic Curves with j-Invariant 0

Zhi Hu, Patrick Longa, and Maozhi Xu

##### Abstract

The Gallant-Lambert-Vanstone (GLV) method is a very efficient technique for accelerating point multiplication on elliptic curves with efficiently computable endomorphisms. Galbraith, Lin and Scott (J. Cryptol. 24(3), 446-469 (2011)) showed that point multiplication exploiting the 2-dimensional GLV method on a large class of curves over GF(p^2) was faster than the standard method on general elliptic curves over GF(p), and left as an open problem to study the case of 4-dimensional GLV on special curves (e.g., j(E) = 0) over GF(p^2). We study the above problem in this paper. We show how to get the 4-dimensional GLV decomposition with proper decomposed coefficients, and thus reduce the number of doublings for point multiplication on these curves to only a quarter. The resulting implementation shows that the 4-dimensional GLV method on a GLS curve runs in about 0.78 the time of the 2-dimensional GLV method on the same curve and in between 0.78-0.87 the time of the 2-dimensional GLV method using the standard method over GF(p). In particular, our implementation reduces by up to 27% the time of the previously fastest implementation of point multiplication on x86-64 processors due to Longa and Gebotys (CHES2010).

Note: Extended benchmark results

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Full version of a journal paper to appear in Designs, Codes and Cryptography
Keywords
Elliptic curvespoint multiplicationGLV methodGLS curves.
Contact author(s)
plonga @ microsoft com
History
2011-10-17: last of 4 revisions
See all versions
Short URL
https://ia.cr/2011/315

CC BY

BibTeX

@misc{cryptoeprint:2011/315,
author = {Zhi Hu and Patrick Longa and Maozhi Xu},
title = {Implementing 4-Dimensional GLV Method on GLS Elliptic Curves with j-Invariant 0},
howpublished = {Cryptology ePrint Archive, Paper 2011/315},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/315}},
url = {https://eprint.iacr.org/2011/315}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.