Abstract
This paper presents new explicit formulae for the point doubling, tripling and addition for ordinary Weierstraß elliptic curves with a point of order 3 and their equivalent Hessian curves over finite fields of characteristic three. The cost of basic point operations is lower than that of all previously proposed ones. The new doubling, mixed addition and tripling formulae in projective coordinates require 3M + 2C, 8M + 1C + 1D and 4M + 4C + 1D respectively, where M, C and D is the cost of a field multiplication, a cubing and a multiplication by a constant. Finally, we present several examples of ordinary elliptic curves in characteristic three for high security levels.
Chapter PDF
Similar content being viewed by others
References
Avanzi, R., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press (2005)
Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography. Cambridge University Press (2005)
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography, vol. 265. Cambridge University Press, New York (1999)
Bernstein, D.J., Kohel, D., Lange, T.: Twisted Hessian Curves, http://www.hyperelliptic.org/EFD/g1p/auto-twistedhessian.html
Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests. Advances in Applied Mathematics 7(4), 385–434 (1986)
Farashahi, R.R., Joye, M.: Efficient Arithmetic on Hessian Curves. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 243–260. Springer, Heidelberg (2010)
Fouquet, M., Gaudry, P., Harley, R.: An Extension of Satoh’s Algorithm and its Implementation. J. Ramanujan Math. Soc. 15, 281–318 (2000)
Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer (2004)
Hesse, O.: Über die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln. Journal für Die Reine und Angewandte Mathematik 10, 68–96 (1844)
Hisil, H., Carter, G., Dawson, E.: New Formulae for Efficient Elliptic Curve Arithmetic. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 138–151. Springer, Heidelberg (2007)
Joye, M., Quisquater, J.-J.: Hessian Elliptic Curves and Side-Channel Attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 402–410. Springer, Heidelberg (2001)
Kim, K.H., Kim, S.I., Choe, J.S.: New Fast Algorithms for Arithmetic on Elliptic Curves over Fields of Characteristic Three. Cryptology ePrint Archive, Report 2007/179 (2007)
Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48, 203–209 (1987)
Koblitz, N.: An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 327–337. Springer, Heidelberg (1998)
López, J., Dahab, R.: Improved Algorithms for Elliptic Curve Arithmetic in tex2html_wrap_inline116. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 201–212. Springer, Heidelberg (1999)
Miller, V.S.: Use of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Negre, C.: Scalar Multiplication on Elliptic Curves Defined over Fields of Small Odd Characteristic. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 389–402. Springer, Heidelberg (2005)
Satoh, T.: The canonical lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting. J. Ramanujan Math. Soc. 15, 247–270 (2000)
Smart, N.P.: The Hessian Form of an Elliptic Curve. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 118–125. Springer, Heidelberg (2001)
Smart, N.P., Westwood, E.J.: Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three. Appl. Algebra Eng. Commun. Comput. 13(6), 485–497 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farashahi, R.R., Wu, H., Zhao, CA. (2013). Efficient Arithmetic on Elliptic Curves over Fields of Characteristic Three. In: Knudsen, L.R., Wu, H. (eds) Selected Areas in Cryptography. SAC 2012. Lecture Notes in Computer Science, vol 7707. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35999-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-35999-6_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35998-9
Online ISBN: 978-3-642-35999-6
eBook Packages: Computer ScienceComputer Science (R0)