nach oben

Journal of Cryptographic Engineering

Erschienen in:

17.05.2018 | Regular Paper

Euclidean addition chains scalar multiplication on curves with efficient endomorphism

verfasst von: Yssouf Dosso, Fabien Herbaut, Nicolas Méloni, Pascal Véron

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 4/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Random Euclidean addition chain generation has proven to be an efficient low memory and SPA secure alternative to standard ECC scalar multiplication methods in the context of fixed base point (Herbaut et al. in Progress in Cryptology-INDOCRYPT 2010, volume 6498 of LNCS. Springer, Berlin, pp 238–261, 2010). In this work, we show how to generalize this method to random point scalar multiplication on elliptic curves with an efficiently computable endomorphism. In order to do so, we generalize results from [21] on the relation of random Euclidean chains generation and elliptic curve point distribution obtained from those chains. We propose a software implementation of our method on various platforms to illustrate the impact of our approach. For that matter, we provide a comprehensive study of the practical computational cost of the modular multiplication when using Java and C standard libraries developed for the arithmetic over large integers.

Vorheriger Artikel A trivial debiasing scheme for Helper Data Systems

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

Nur mit Berechtigung zugänglich

Acıiçmez, O., Brumley, B.B., Grabher, P.: New results on instruction cache attacks. In: Proceedings of CHES (2010)

Baldwin, B., Goundar, R.R., Hamilton, M., Marnane, W.P.: Co–z ECC scalar multiplications for hardware, software and hardware-software co-design on embedded systems. J. Cryptogr. Eng. 2(4), 221–240 (2012)CrossRef

Benger, N., Pol, J., Smart, N.P., Yarom, Y.: ooh aah... just a little bit: A small amount of side channel can go a long way. In: Proceedings of CHES 2014, volume 8731, pp. 75–92, New York, NY, USA. Springer, New York (2014)

Bernstein, D.J., Lange, T.: Explicit-Formulas Database. https://www.hyperelliptic.org/EFD/

Brauer, A.: On addition chains. Bull. Am. Math. Soc. 45(10), 736–739 (1939)MathSciNetCrossRef

Brumley, B.B.: Faster software for fast endomorphisms. In: Constructive Side-Channel Analysis and Secure Design—6th International Workshop, COSADE 2015, pp. 127–140 (2015)CrossRef

Brumley, B.B., Hakala, R.M.: Cache-timing template attacks. In: Advances in Cryptology—ASIACRYPT 2009: 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, pp. 667–684. Springer, Berlin (2009)CrossRef

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

Costello, C., Hisil, H., Smith, B.: Faster compact Diffie–Hellman: endomorphisms on the x-line. In: Advances in Cryptology—EUROCRYPT 2014, pp. 183–200. Springer (2014)

10.

Costello, C., Longa, P.: Four\(\mathbb{Q}\): four-dimensional decompositions on a \(\mathbb{Q}\)-curve over the Mersenne prime. In: Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security on Advances in cryptology—ASIACRYPT 2015. Part I. Auckland, New Zealand, November 29 – December 3, 2015, pp. 214–235. Springer, Berlin (2015)

11.

Sica, F., Ciet, M., Quisquater, J-J.: Analysis of the Gallant–Lambert–Vanstone method based on efficient endomorphisms: elliptic and hyperelliptic curves. In: Selected Areas in Cryptography, volume 2595 of LNCS, pp. 21–36. Springer (2003)

12.

Faz-Hernández, A., Longa, P., Sánchez, A.H.: Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves (extended version). J. Cryptogr. Eng. 5(1), 31–52 (2015)CrossRef

13.

Galbraith, S., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Cryptol. 24(3), 446–469 (2011)MathSciNetCrossRef

14.

Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Advances in Cryptology—EUROCRYPT 2009, volume 5479 of LNCS, pp. 518–535. Springer, Berlin (2009)CrossRef

15.

Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Advances in Cryptology—CRYPTO, volume 2139 of LNCS, pp. 190–200. Springer (2001)

16.

Goundar, R.R., Joye, M., Miyaji, A.: Co–Z addition formulae and binary ladders on elliptic curves—(extended abstract). In: Cryptographic Hardware and Embedded Systems, CHES 2010, pp. 65–79 (2010)CrossRef

17.

Goundar, R.R., Joye, M.: Inversion-free arithmetic on elliptic curves through isomorphisms. J. Cryptogr. Eng. 6, 1–13 (2016)CrossRef

18.

Goundar, Raveen R., Joye, Marc, Miyaji, Atsuko, Rivain, Matthieu, Venelli, Alexandre: Scalar multiplication on Weierstraß elliptic curves from co–z arithmetic. J. Cryptogr. Eng. 1(2), 161–176 (2011)CrossRef

19.

Guillevic, A., Ionica, S.: Four-dimensional GLV via the weil restriction. In: Advances in Cryptology - ASIACRYPT 2013, pp. 79–96 (2013)CrossRef

20.

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

21.

Herbaut, F., Liardet, P.-Y., Méloni, N., Téglia, Y., Véron, P.: Random euclidean addition chain generation and its application to point multiplication. In: Progress in Cryptology—INDOCRYPT 2010, volume 6498 of LNCS, pp. 238–261. Springer, Heidelberg (2010)CrossRef

22.

Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: Advances in cryptology—ASIACRYPT 2008. In: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7–11, 2008, pp. 326–343. Springer, Berlin (2008)CrossRef

23.

Hutter, M., Joye, M., Sierra, Y.: Memory-constrained implementations of elliptic curve cryptography in co–Z coordinate representation. In: Progress in Cryptology—AFRICACRYPT 2011, pp. 170–187 (2011)MATH

24.

Käsper, E.: Fast elliptic curve cryptography in openssl. In: Proceedings of the 2011 International Conference on Financial Cryptography and Data Security, FC’11, pp. 27–39. Springer (2012)

25.

Liu, Zhe, Wang, Husen, Großschädl, Johann, Hu, Zhi, Verbauwhede, Ingrid: Vlsi implementation of double-base scalar multiplication on a twisted edwards curve with an efficiently computable endomorphism. IACR Cryptol. ePrint Arch. 2015, 421 (2015)

26.

Longa, P., Miri, A.: New Composite Operations and Precomputation Scheme for Elliptic Curve Cryptosystems over Prime Fields, pp. 229–247. Springer, Berlin (2008)

27.

Longa, Patrick, Sica, Francesco: Four-dimensional Gallant–Lambert–Vanstone scalar multiplication. J. Cryptol. 27(2), 248–283 (2014)MathSciNetCrossRef

28.

Meloni, N.: New point addition formulae for ECC applications. In: Arithmetic of Finite Fields, volume 4547 of LNCS, pp. 189–201. Springer, Berlin (2007)

29.

Möller, B.: Improved techniques for fast exponentiation. In: Information Security and Cryptology—ICISC 2002, volume 2587 of LNCS, pp. 298–312. Springer, Heidelberg (2003)

30.

Montgomery, P.L.: Evaluating recurrences of form \(x\_{m+n}= f(x\_m,x\_n,x\_{m-n})\) via Lucas chains (1983). https://cr.yp.to/bib/1992/montgomery-lucas.pdf

31.

Park, Y.-H., Jeong, S., Kim, C., Lim, J.: An alternate decomposition of an integer for faster point multiplication on certain elliptic curves. In: Public Key Cryptography, volume 2274 of LNCS, pp. 323–334. Springer, Heidelberg (2002)

32.

Smith, B.: Families of fast elliptic curves from \(\mathbb{q}\)-curves. In: Advances in Cryptology - ASIACRYPT 2013, pp. 61–78 (2013)CrossRef

33.

Solinas, J.A.: Low-weight binary representations for pairs of integers. Technical report, University of Waterloo. Department of Combinatorics and Optimization (2001)

34.

Thurber, E.G.: On addition chains \(l(mn)\le l(n) -b\) and lower bounds for \(c(r)\). Duke Math. J. 40, 907–913 (1973)MathSciNetCrossRef

35.

Yarom, Y., Falkner, K.: Flush+reload: a high resolution, low noise, l3 cache side-channel attack. In: 23rd USENIX Security Symposium (USENIX Security 14), pp. 719–732, San Diego, CA. USENIX Association (2014)

Titel: Euclidean addition chains scalar multiplication on curves with efficient endomorphism
verfasst von: Yssouf Dosso
Fabien Herbaut
Nicolas Méloni
Pascal Véron
Publikationsdatum: 17.05.2018
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Cryptographic Engineering / Ausgabe 4/2018
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-018-0190-0

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"

Weitere Artikel der Ausgabe 4/2018

Scan-based side channel attack on stream ciphers and its prevention

Template attacks versus machine learning revisited and the curse of dimensionality in side-channel analysis: extended version

Another dimension in integrated circuit trust

Arithmetic of -adic expansions for lightweight Koblitz curve cryptography

A class of safe and efficient binary Edwards curves

A trivial debiasing scheme for Helper Data Systems