Abstract
This paper considers a generalized form for Hessian curves. The family of generalized Hessian curves covers more isomorphism classes of elliptic curves. Over a finite field \(\mathbb{F}_q\), it is shown to be equivalent to the family of elliptic curves with a torsion subgroup isomorphic to ℤ/3ℤ.
This paper provides efficient unified addition formulas for generalized Hessian curves. The formulas even feature completeness for suitably chosen parameters.
This paper also presents extremely fast addition formulas for generalized binary Hessian curves. The fastest projective addition formulas require 9M + 3S, where M is the cost of a field multiplication and S is the cost of a field squaring. Moreover, very fast differential addition and doubling formulas are provided that need only 5M + 4S when the curve is chosen with small curve parameters.
Chapter PDF
Similar content being viewed by others
References
Al-Daoud, E., Mahmod, R., Rushdan, M., Kiliçman, A.: A new addition formula for elliptic curves over GF(2n). IEEE Trans. Computers 51(8), 972–975 (2002)
Avanzi, R., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005)
Avanzi, R.M., Dimitrov, V.S., Doche, C., Sica, F.: Extending scalar multiplication using double bases. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 130–144. Springer, Heidelberg (2006)
Bernstein, D.J., Lange, T.: Explicit-formulas database, http://www.hyperelliptic.org/EFD/
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)
Bernstein, D.J., Lange, T., Farashahi, R.R.: Binary Edwards curves. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 244–265. Springer, Heidelberg (2008)
Bersntein, D.J., Kohel, D., Lange, T.: Twisted Hessian curves, http://www.hyperelliptic.org/EFD/g1p/auto-twistedhessian.html
Billet, O., Joye, M.: The Jacobi model of an elliptic curve and side-channel analysis. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 34–42. Springer, Heidelberg (2003)
Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography. Cambridge University Press, Cambridge (2005)
Brier, É., Déchène, I., Joye, M.: Unified point addition formulæ for elliptic curve cryptosystems. In: Embedded Cryptographic Hardware: Methodologies & Architectures, pp. 247–256. Nova Science Publishers (2004)
Brier, É., Joye, M.: Weierstraß elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002)
Cassels, J.W.S.: Lectures on Elliptic Curves. Cambridge University Press, Cambridge (1991)
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)
Dimitrov, V.S., Imbert, L., Mishra, P.K.: Efficient and secure elliptic curve point multiplication using double-base chains. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 59–78. Springer, Heidelberg (2005)
Doche, C., Imbert, L.: Extended double-base number system with applications to elliptic curve cryptography. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 335–348. Springer, Heidelberg (2006)
Farashahi, R.R.: On the number of distinct Legendre, Jacobi and Hessian curves (Preprint)
Farashahi, R.R., Shparlinski, I.E.: On the number of distinct elliptic curves in some families. Designs, Codes and Cryptography 54(1), 83–99 (2010)
Gaudry, P., Lubicz, D.: The arithmetic of characteristic 2 Kummer surfaces. Finite Fields and Applications 15, 246–260 (2009)
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)
Higuchi, A., Takagi, N.: A fast addition algorithm for elliptic curve arithmetic in GF(2n) using projective coordinates. Inf. Process. Lett. 76(3), 101–103 (2000)
Hisil, H., Carter, G., Dawson, E.: New formulæ 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)
Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Faster group operations on elliptic curves. In: Brankovic, L., Susilo, W. (eds.) Australasian Information Security Conference (AISC 2009). Conferences in Research and Practice in Information Technology (CRPIT), vol. 98, pp. 7–19 (2009)
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.: A new method for speeding up arithmetic on elliptic curves over binary fields. Cryptology ePrint Archive, Report 2007/181 (2007)
Knapp, A.: Elliptic Curves. Princeton University Press, Princeton (1992)
Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48(177), 203–209 (1987)
Liardet, P.-Y., Smart, N.P.: Preventing SPA/DPA in ECC systems using the Jacobi form. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 391–401. Springer, Heidelberg (2001)
López, J., Dahab, R.: Fast multiplication on elliptic curves over GF(2n) without precomputation. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 316–327. Springer, Heidelberg (1999)
López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(2n). 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)
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48(177), 243–264 (1987)
Silverman, J.H.: The Arithmetic of Elliptic Curves. Springer, Heidelberg (1986)
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)
Stam, M.: On Montgomery-like representationsfor elliptic curves over GF(2n). In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 240–253. Springer, Heidelberg (2002)
Washington, L.C.: Elliptic Curves: Number Theory and Cryptography. CRC Press, Boca Raton (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farashahi, R.R., Joye, M. (2010). Efficient Arithmetic on Hessian Curves. In: Nguyen, P.Q., Pointcheval, D. (eds) Public Key Cryptography – PKC 2010. PKC 2010. Lecture Notes in Computer Science, vol 6056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13013-7_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-13013-7_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13012-0
Online ISBN: 978-3-642-13013-7
eBook Packages: Computer ScienceComputer Science (R0)