[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Extended Double-Base Number System with Applications to Elliptic Curve Cryptography

  • Conference paper
Progress in Cryptology - INDOCRYPT 2006 (INDOCRYPT 2006)

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

Included in the following conference series:

Abstract

We investigate the impact of larger digit sets on the length of Double-Base Number system (DBNS) expansions. We present a new representation system called extended DBNS whose expansions can be extremely sparse. When compared with double-base chains, the average length of extended DBNS expansions of integers of size in the range 200–500 bits is approximately reduced by 20% using one precomputed point, 30% using two, and 38% using four. We also discuss a new approach to approximate an integer n by d2a3b where d belongs to a given digit set. This method, which requires some precomputations as well, leads to realistic DBNS implementations. Finally, a left-to-right scalar multiplication relying on extended DBNS is given. On an elliptic curve where operations are performed in Jacobian coordinates, improvements of up to 13% overall can be expected with this approach when compared to window NAF methods using the same number of precomputed points. In this context, it is therefore the fastest method known to date to compute a scalar multiplication on a generic elliptic curve.

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

    Google Scholar 

  2. Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48, 203–209 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  3. Koblitz, N.: Hyperelliptic cryptosystems. J. Cryptology 1, 139–150 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  4. Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic curves in cryptography. London Mathematical Society Lecture Note Series, vol. 265. Cambridge University Press, Cambridge (1999)

    MATH  Google Scholar 

  5. Hankerson, D., Menezes, A.J., Vanstone, S.A.: Guide to elliptic curve cryptography. Springer, Berlin (2003)

    Google Scholar 

  6. Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Nguyen, K., Lange, T., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. In: Discrete Mathematics and its Applications. CRC Press, Inc., Boca Raton (2005)

    Google Scholar 

  7. Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography. London Mathematical Society Lecture Note Series, vol. 317. Cambridge University Press, Cambridge (2005)

    Book  MATH  Google Scholar 

  8. Doche, C.: Exponentiation. In: [6], pp. 145–168

    Google Scholar 

  9. Morain, F., Olivos, J.: Speeding up the Computations on an Elliptic Curve using Addition-Subtraction Chains. Inform. Theor. Appl. 24, 531–543 (1990)

    MATH  MathSciNet  Google Scholar 

  10. Dimitrov, V.S., Jullien, G.A., Miller, W.C.: Theory and applications of the double-base number system. IEEE Trans. on Computers 48, 1098–1106 (1999)

    Article  Google Scholar 

  11. Miyaji, A., Ono, T., Cohen, H.: Efficient Elliptic Curve Exponentiation. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 282–291. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  13. Dimitrov, V.S., Jullien, G.A., Miller, W.C.: An algorithm for modular exponentiation. Information Processing Letters 66, 155–159 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  14. Berthé, V., Imbert, L.: On converting numbers to the double-base number system. In: Luk, F.T. (ed.) Advanced Signal Processing Algorithms, Architecture and Implementations XIV. Proceedings of SPIE, vol. 5559, pp. 70–78 (2004)

    Google Scholar 

  15. Ciet, M., Sica, F.: An Analysis of Double Base Number Systems and a Sublinear Scalar Multiplication Algorithm. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 171–182. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  16. Avanzi, R.M., Sica, F.: Scalar Multiplication on Koblitz Curves Using Double Bases. In: Nguyên, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 131–146. Springer, Heidelberg (2006); See also Cryptology ePrint Archive, Report 2006/067, http://eprint.iacr.org/

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  18. Doche, C., Imbert, L.: Extended Double-Base Number System with Applications to Elliptic Curve Cryptography (2006); Full version of the present paper, see Cryptology ePrint Archive, http://eprint.iacr.org/

  19. Doche, C.: A set of PARI/GP functions to compute DBNS expansions, http://www.ics.mq.edu.au/~doche/dbns_basis.gp

  20. Doche, C., Lange, T.: Arithmetic of Elliptic Curves. In: [6], pp. 267–302

    Google Scholar 

  21. Ciet, M., Joye, M., Lauter, K., Montgomery, P.L.: Trading inversions for multiplications in elliptic curve cryptography. Des. Codes Cryptogr. 39, 189–206 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  22. Dimitrov, V.S., Järvinen, K.U., Jacobson Jr., M.J., Chan, W.F., Huang, Z.: FPGA Implementation of Point Multiplication on Koblitz Curves Using Kleinian Integers. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 445–459. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  23. Avanzi, R.M., et al.: Extending Scalar Multiplication using Double Bases. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 130–144. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computing, Macquarie University, Australia

    Christophe Doche

  2. LIRMM, CNRS, Université Montpellier 2, UMR 5506, France, & ATIPS, CISaC, University of Calgary, Canada

    Laurent Imbert

Authors
  1. Christophe Doche
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Laurent Imbert
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Indian Statistical Institute, 205, B.T. Road, Kolkata, India

    Rana Barua

  2. Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600, Eindhoven, MB, Netherlands

    Tanja Lange

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Doche, C., Imbert, L. (2006). Extended Double-Base Number System with Applications to Elliptic Curve Cryptography. In: Barua, R., Lange, T. (eds) Progress in Cryptology - INDOCRYPT 2006. INDOCRYPT 2006. Lecture Notes in Computer Science, vol 4329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11941378_24

Download citation

  • DOI: https://doi.org/10.1007/11941378_24

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-49767-7

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

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation