nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Fast Scalar Multiplication for Elliptic Curves over Binary Fields by Efficiently Computable Formulas

verfasst von : Saud Al Musa, Guangwu Xu

Erschienen in: Progress in Cryptology – INDOCRYPT 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper considers efficient scalar multiplication of elliptic curves over binary fields with a twofold purpose. Firstly, we derive the most efficient 3P formula in \(\lambda \)-projective coordinates and 5P formula in both affine and \(\lambda \)-projective coordinates. Secondly, extensive experiments have been conducted to test various multi-base scalar multiplication methods (e.g., greedy, ternary/binary, multi-base NAF, and tree-based) by integrating our fast formulas. The experiments show that our 3P and 5P formulas had an important role in speeding up the greedy, the ternary/binary, the multi-base NAF, and the tree-based methods over the NAF method. We also establish an efficient 3P formula for Koblitz curves and use it to construct an improved set for the optimal pre-computation of window TNAF.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Efficient Optimal Ate Pairing at 128-Bit Security Level

Nächstes Kapitel Field Lifting for Smaller UOV Public Keys

Nur mit Berechtigung zugänglich

Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Nguyen, K., Lange, T., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, Boca Raton (2005)MATH

Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: Optimizing double-base elliptic-curve single-scalar multiplication. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 167–182. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77026-8_13 CrossRef

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

Blake, I.F., Murty, V.K., Xu, G.: A note on window \(\tau \)-NAF algorithm. Inf. Process. Lett. 95(5), 496–502 (2005)MathSciNetCrossRefMATH

Blake, I.F., Murty, V.K., Xu, G.: Nonadjacent radix-\(\tau \) expansions of integers in euclidean imaginary quadratic number fields. Can. J. Math. 60, 1267–1282 (2008)MathSciNetCrossRefMATH

Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (1999)CrossRefMATH

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

Dimitrov, V., Imbert, L., Mishra, P.K.: The double-base number system and its application to elliptic curve cryptography. Math. Comput. 77(262), 1075–1104 (2008)MathSciNetCrossRefMATH

Doche, C.: On the enumeration of double-base chains with applications to elliptic curve cryptography. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 297–316. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_16

10.

Doche, C., Habsieger, L.: A tree-based approach for computing double-base chains. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 433–446. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70500-0_32 CrossRef

11.

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). https://doi.org/10.1007/11941378_24 CrossRef

12.

Doche, C., Kohel, D.R., Sica, F.: Double-base number system for multi-scalar multiplications. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 502–517. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_29 CrossRef

13.

Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 518–535. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_30 CrossRef

14.

Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_11 CrossRef

15.

Hankerson, D., Karabina, K., Menezes, A.: Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields. IEEE Trans. Comput. 58(10), 1411–1420 (2009)MathSciNetCrossRefMATH

16.

Hankerson, D., López Hernandez, J., Menezes, A.: Software implementation of elliptic curve cryptography over binary fields. In: Koç, Ç.K., Paar, C. (eds.) CHES 2000. LNCS, vol. 1965, pp. 1–24. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44499-8_1 CrossRef

17.

Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2004). https://doi.org/10.1007/b97644 MATH

18.

Koblitz, N.: CM-curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_22

19.

Koblitz, N.: Elliptic curve cryptosystems. Math. Computat. 48(177), 203–209 (1987)MathSciNetCrossRefMATH

20.

Lange, T.: A note on López-Dahab coordinates. Cryptology ePrint Archive, Report 2004/323 (2004). https://eprint.iacr.org

21.

Lenstra, A., Verheul, E.: Selecting cryptographic key sizes. J. Cryptol. 14, 255–293 (2001)MathSciNetCrossRefMATH

22.

Longa, P.: Accelerating the scalar multiplication on elliptic curve cryptosystems over prime fields. Cryptology ePrint Archive, Report 2008/100 (2008). https://eprint.iacr.org

23.

Longa, P., Gebotys, C.: Fast multibase methods and other several optimizations for elliptic curve scalar multiplication. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 443–462. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00468-1_25 CrossRef

24.

López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(2ⁿ). In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 201–212. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48892-8_16 CrossRef

25.

Méloni, N., Hasan, M.: Efficient double bases for scalar multiplication. IEEE Trans. Comput. 64, 2204–2212 (2015)MathSciNetCrossRefMATH

26.

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). https://doi.org/10.1007/3-540-39799-X_31

27.

Mishra, P.K., Dimitrov, V.: Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation. In: Garay, J.A., Lenstra, A.K., Mambo, M., Peralta, R. (eds.) ISC 2007. LNCS, vol. 4779, pp. 390–406. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75496-1_26 CrossRef

28.

Oliveira, T., López, J., Aranha, D.F., Rodriguez-Henriquez, F.: Two is the fastest prime: lambda coordinates for binary elliptic curves. J. Cryptogr. Eng. 4(1), 3–17 (2014)CrossRef

29.

Solinas, J.A.: Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19(2–3), 195–249 (2000)MathSciNetCrossRefMATH

30.

Trost, W., Xu, G.: On the optimal pre-computation of window tNAF for Koblitz curves. IEEE Trans. Comput. 65, 2918–2924 (2016)MathSciNetCrossRefMATH

31.

Yasin, S., Muda, Z.: Tripling formulae of elliptic curve over binary field in Lopez-Dahab model. J. Theor. Appl. Inf. Technol. 75(2), 212–217 (2015)

32.

Yu, W., Kim, K.H., Jo, M.S.: New fast algorithms for elliptic curve arithmetic in affine coordinates. In: Tanaka, K., Suga, Y. (eds.) IWSEC 2015. LNCS, vol. 9241, pp. 56–64. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22425-1_4 CrossRef

33.

Yu, W., Wang, K., Li, B., Tian, S.: Triple-base number system for scalar multiplication. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) AFRICACRYPT 2013. LNCS, vol. 7918, pp. 433–451. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38553-7_26 CrossRef

34.

Digital Signature Standard (DSS): FIPS PUB. 186–4 (2013)

35.

The GNU Multiple Precision Arithmetic Library. http://www.gmplib.org

Titel: Fast Scalar Multiplication for Elliptic Curves over Binary Fields by Efficiently Computable Formulas
verfasst von: Saud Al Musa
Guangwu Xu
Verlag: Springer International Publishing
Buch: Progress in Cryptology – INDOCRYPT 2017
Print ISBN: 978-3-319-71666-4

Electronic ISBN: 978-3-319-71667-1

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-71667-1_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner