Abstract
The Frobenius expansion is a method to speed up scalar multiplication on elliptic curves. Nigel Smart gave a Frobenius expansion method for elliptic curves defined over odd prime fields. Gallant, Lambert and Vanstone suggested that efficiently computable endomorphisms other than Frobenius endomorphisms can be used for fast scalar multiplication. In this paper we show that these two kinds of endomorphisms can be used together for a certain class of curves, and we present a new expansion method for elliptic curves over odd prime fields. Our experimental results show that the throughputs of the known scalar multiplication algorithms are improved by 7.6 ~ 17.3% using the new expansion method.
This work was supported by the Brain Korea 21 Project and the MOST grant M6- 0203-00-0039.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D.V. Bailey and C. Paar. Optimal extension fields for fast arithmetic in public key algorithms. In Advances in Cryptology-CRYPTO 98, volume 1462 of LNCS,pages 472–485. Springer-Verlag, 1998. 264, 265, 275
D.V. Bailey and C. Paar. Efficient arithmetic in finite field extensions with application in elliptic curve cryptography. Journal of Cryptology, 14(3):153–176, 2001. 264, 265, 275, 276
J.H. Cheon, S. Park, S. Park, and D. Kim. Two efficient algorithms for arithmetic of elliptic curves using Frobenius map. In Public Key Cryptography 98, volume1431 of LNCS, pages 195–202. Springer-Verlag, 1998. 264
R. Gallant, R. Lambert, and S. Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms. In Advances in Cryptology-CRYPTO 2001, volume 2139 of LNCS, pages 190–200. Springer-Verlag, 2001. 264, 265, 266, 271, 277
G.H. Hardy and E.M. Wright.An Introduction to the Theory of Numbers. Oxford University Press, 3rd edition, 1954. 267, 279
T. Kobayashi. Base-ø method for elliptic curves over OEF. IEICE Trans. Fundamentals, E83-A(4):679–686, 2000. 264, 265, 271, 272, 275
T. Kobayashi, H. Morita, K. Kobayashi, and F. Hoshino. Fast elliptic curve algorithm combining Frobenius map and table reference to adapt to higher characteristic. In Advances in Cryptology-EUROCRYPT 99, volume 1592 of LNCS, pages 176–189. Springer-Verlag, 1999. 264, 265, 271, 272, 276
N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48:203–209, 1987. 264
N. Koblitz. CM-curves with good cryptographic properties. In Advances in Cryptology-CRYPTO 91, volume 576 of LNCS, pages 279–287. Springer-Verlag, 1991. 264
C.H. Lim and H. S. Hwang. Speeding up elliptic scalar multiplication with precomputation. In Information Security and Cryptology-ICISC 99, volume 1787 of LNCS, pages 102–119. Springer-Verlag, 1999. 264, 265, 271, 273
C. H. Lim and P. J. Lee. More flexible exponentiation with precomputation. In Advances in Cryptology-CRYPTO 94, volume 839 of LNCS, pages 95–107. Springer-Verlag, 1994. 264, 273, 281
W. Meier and O. Staffelbach. Efficient multiplication on certain non-supersingular elliptic curves. In Advances in Cryptology-CRYPTO 92, volume 740 of LNCS, pages 333–344. Springer-Verlag, 1992. 264
A. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, 1993. 265
V. Miller. Use of elliptic curves in cryptography. In Advances in Cryptology-CRYPTO 85, volume 218 of LNCS, pages 417–428. Springer-Verlag, 1986. 264
B. Möller. Algorithms for multi-exponentiation. In Selected Areas in Cryptography-SAC 2001, volume 2259 of LNCS, pages 165–180. Springer-Verlag, 2001. 277
F. Morain and J. Olivos. Speeding up the computations on an elliptic curve using addition-subtraction chains. Theoretical Informatics and Applications, 24:531–543, 1990. 264
V. Müller. Fast multiplication on elliptic curves over small fields of characteristic two. Journal of Cryptology, 11:219–234, 1998. 264
J.R. Silverman. The Arithmetic of Elliptic Curves. Springer-Verlag, 1986. 265, 267
N.P. Smart. Elliptic curve cryptosystems over small fields of odd characteristic. Journal of Cryptology, 12:141–151, 1999. 264, 266, 272, 275
J.A. Solinas. An improved algorithm for arithmetic on a family of elliptic curves. In Advances in Cryptology-CRYPTO 97, volume 1294 of LNCS, pages 357–371. Springer-Verlag, 1997. 264
J.A. Solinas. Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography, 19:195–249, 2000. 264
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Park, TJ., Lee, MK., Park, K. (2003). New Frobenius Expansions for Elliptic Curves with Efficient Endomorphisms. In: Lee, P.J., Lim, C.H. (eds) Information Security and Cryptology — ICISC 2002. ICISC 2002. Lecture Notes in Computer Science, vol 2587. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36552-4_19
Download citation
DOI: https://doi.org/10.1007/3-540-36552-4_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00716-6
Online ISBN: 978-3-540-36552-5
eBook Packages: Springer Book Archive