Efficient Arithmetic on Subfield Elliptic Curves over Small Finite Fields of Odd Characteristic | SpringerLink
Skip to main content
Springer Nature Link
Log in

Efficient Arithmetic on Subfield Elliptic Curves over Small Finite Fields of Odd Characteristic

  • Conference paper
Information Security Practice and Experience (ISPEC 2008)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 4991))

  • 810 Accesses

Abstract

In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the performance of the algorithm used. For integer radices, the non-adjacent form (NAF) [21] and its generalizations (e.g., the generalized non-adjacent form (GNAF) [6] and the radix-r non-adjacent form (rNAF) [28]) have been proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, the Frobenius expansions of the scalars can be used for improving efficiency [25]. Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to the Frobenius expansion, namely τ-adic NAF techniques on Koblitz curves [16,27,3] and hyperelliptic Koblitz curves [10]. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and the Frobenius expansion, and propose two new efficient recoding methods of scalars on more general family of subfield elliptic curves in odd characteristic. We also prove that the non-zero densities for the new methods are same as those for the original GNAF and rNAF. As a result, the speed of the proposed methods improve between 8% and 50% over that for the Frobenius expansion method.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Avanzi, R., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: The Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005)

    Google Scholar 

  2. Avanzi, R.M., Heuberger, C., Prodinger, H.: Minimality of the Hamming Weight of the τ-NAF for Koblitz Curves and Improved Combination with Point Halving. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 332–344. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Blake, I.F., Murty, V.K., Xu, G.: Nonadjacent radix-τ Expansions of Integers in Euclidean Imaginary Quadratic Number Fields. In: Ganita Laboratory (November 2004), http://www.erin.utoronto.ca/~w3ganita/radix_t.pdf

  4. Blake, I., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography. LMS Lecture Note Series, vol. 265. Cambridge University Press, Cambridge (1999)

    MATH  Google Scholar 

  5. Blake, I., Seroussi, G., Smart, N.P. (eds.): Advances in Elliptic Curve Cryptography. LMS Lecture Note Series, vol. 317. Cambridge University Press, Cambridge (2005)

    MATH  Google Scholar 

  6. Clark, W.E., Liang, J.J.: On arithmetic weight for a general radix representation of integers. IEEE Transactions on Information Theory IT-19, 823–826 (1973)

    Article  MathSciNet  Google Scholar 

  7. Cohen, H., Miyaji, A., Ono, T.: Efficient elliptic curve exponentiation using mixed coordinates. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  8. Diem, C.: A study on theoretical and practical aspects of Weil-restriction of varieties. Ph.D. thesis, Universität Gesamthochschule Essen (2001)

    Google Scholar 

  9. Diem, C.: The GHS-attack in odd characteristic. J. Ramanujan Math. Soc. 18, 1–32 (2003)

    MATH  MathSciNet  Google Scholar 

  10. Günther, C., Lange, T., Stein, A.: Speeding up the Arithmetic on Koblitz Curves of Genus Two. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 106–117. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  11. Gallant, R., Lambert, R., Vanstone, S.: Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  12. Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, Heidelberg (2004)

    MATH  Google Scholar 

  13. Hakuta, K., Sato, H., Takagi, T.: Efficient Arithmetic on Subfield Elliptic Curves over Small Finite Fields of Odd Characteristic. Cryptology ePrint Archive, Report 2005/454 (2005), http://eprint.iacr.org/2005/454

  14. Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48, 203–209 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  15. Koblitz, N.: CM-curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992)

    Google Scholar 

  16. 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)

    Google Scholar 

  17. Lange, T.: Efficient Arithmetic on Hyperelliptic Koblitz Curves. Ph.D. thesis, University of Essen (2001)

    Google Scholar 

  18. Müller, V.: Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two. Journal of Cryptology 11, 219–234 (1998)

    Article  MATH  Google Scholar 

  19. Miller, V.: Uses of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)

    Google Scholar 

  20. Park, T.J., Lee, M.K., Park, K.: New Frobenius Expansions for Elliptic Curves with Efficient Endomorphisms. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 264–282. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  21. Reitwiesner, G.W.: Binary arithmetic. Advances in Computers 1, 231–308 (1960)

    MathSciNet  Google Scholar 

  22. Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii Mathematici Universitatis Sancti Pauli 47, 81–92 (1998)

    MATH  MathSciNet  Google Scholar 

  23. Semaev, I.A.: Evaluation of discrete logarithms on some elliptic curves. Mathematics of Computation 67, 353–356 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  24. Silverman, J.H.: The Arithmetic of Elliptic Curves. In: GTM 106, Springer, Heidelberg (1986)

    Google Scholar 

  25. Smart, N.P.: Elliptic Curve Cryptosystems over Small Fields of Odd Characteristic. Journal of Cryptology 12, 141–151 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  26. Smart, N.P.: The discrete logarithm problem on elliptic curves of trace one. Journal of Cryptology 12, 193–196 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  27. Solinas, J.A.: Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography 19, 195–249 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  28. Takagi, T., Yen, S.M., Wu, B.C.: Radix-r Non-adjacent Form. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 99–110. Springer, Heidelberg (2004)

    Google Scholar 

  29. van Lint, J.H.: Introduction to coding theory. In: GTM 86, Springer, Heidelberg (1982)

    Google Scholar 

  30. Washington, L.C.: Elliptic Curves: Number Theory and Cryptography. CRC Press, Boca Raton (2003)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Hitachi, Ltd., Systems Development Laboratory, 1099, Ohzenji, Asao-ku, Kawasaki, 215-0013, Japan

    Keisuke Hakuta & Hisayoshi Sato

  2. School of Systems Information Science, Future University - Hakodate, 116-2, Kamedanakano-cho, Hakodate, 041-8655, Japan

    Tsuyoshi Takagi

Authors
  1. Keisuke Hakuta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hisayoshi Sato
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tsuyoshi Takagi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Liqun Chen Yi Mu Willy Susilo

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hakuta, K., Sato, H., Takagi, T. (2008). Efficient Arithmetic on Subfield Elliptic Curves over Small Finite Fields of Odd Characteristic . In: Chen, L., Mu, Y., Susilo, W. (eds) Information Security Practice and Experience. ISPEC 2008. Lecture Notes in Computer Science, vol 4991. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79104-1_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-79104-1_22

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-79103-4

  • Online ISBN: 978-3-540-79104-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation