nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Acceleration of Index Calculus for Solving ECDLP over Prime Fields and Its Limitation

verfasst von : Momonari Kudo, Yuki Yokota, Yasushi Takahashi, Masaya Yasuda

Erschienen in: Cryptology and Network Security

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

In 2018, Amadori et al. proposed a new variant of index calculus to solve the elliptic curve discrete logarithm problem (ECDLP), using Semaev’s summation polynomials. The variant drastically decreases the number of required Gröbner basis computations, and it outperforms other index calculus algorithms for the ECDLP over prime fields. In this paper, we provide several improvements to accelerate to solve systems of multivariate equations arising in the variant. A main improvement is to apply the hybrid method, which mixes exhaustive search and Gröbner bases techniques to solve multivariate systems over finite fields. We also make use of symmetries of summation polynomials. We show experimental results of our improvements, and give their complexity analysis to discuss a limitation of our acceleration in both theory and practice.

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 Solving LWR via BDD Strategy: Modulus Switching Approach

Nächstes Kapitel Several MILP-Aided Attacks Against SNOW 2.0

Amadori, A., Pintore, F., Sala, M.: On the discrete logarithm problem for prime-field elliptic curves. Finite Fields Appl. 51, 168–182 (2018)MathSciNetCrossRef

Bernstein, D.J., et al.: Faster elliptic-curve discrete logarithms on FPGAs. IACR Cryptology ePrint Archive 2016/382 (2016)

Bettale, L., Faugère, J.C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3(3), 177–197 (2009)MathSciNetCrossRef

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

Bos, J.W., Kaihara, M.E., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction. Int. J. Appl. Cryptogr. 2(3), 212–228 (2012)MathSciNetCrossRef

Caminata, A., Gorla, E.: Solving multivariate polynomial systems and an invariant from commutative algebra. arXiv preprint arXiv:1706.06319 (2017)

Caviglia, G., Sbarra, E.: Characteristic-free bounds for the castelnuovo-mumford regularity. Compos. Math. 141(6), 1365–1373 (2005)MathSciNetCrossRef

Cohen, H., et al.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005)CrossRef

Diem, C.: On the discrete logarithm problem in elliptic curves. Compos. Math. 147(01), 75–104 (2011)MathSciNetCrossRef

10.

Eisenbud, D.: The Geometry of Syzygies: A Second Course in Algebraic Geometry and Commutative Algebra. Graduate Texts in Mathematics, vol. 229. Springer, New York (2005). https://doi.org/10.1007/b137572CrossRefMATH

11.

Faugère, J.C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139(1–3), 61–88 (1999)MathSciNetCrossRef

12.

Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: International Symposium on Symbolic and Algebraic Computation-ISSAC 2002, pp. 75–83. ACM (2002)

13.

Faugère, J.-C., Perret, L., Petit, C., Renault, G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 27–44. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_4CrossRefMATH

14.

Galbraith, S.D., Gaudry, P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51–72 (2016)MathSciNetCrossRef

15.

Galbraith, S.D., Gebregiyorgis, S.W.: Summation polynomial algorithms for elliptic curves in characteristic two. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 409–427. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13039-2_24CrossRefMATH

16.

Gary, M., Daniela, M.: A few more index calculus algorithms for the elliptic curve discrete logarithm problem. Cryptology ePrint Archive: Report 2017/1262 (2017). https://eprint.iacr.org/2017/1262

17.

Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symb. Comput. 44(12), 1690–1702 (2009)MathSciNetCrossRef

18.

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

19.

Hashemi, A., Seiler, W.M.: Dimension-dependent upper bounds for grobner bases. arXiv preprint arXiv:1705.02776 (2017). https://arxiv.org/abs/1705.02776

20.

Kleinjung, T., et al.: Factorization of a 768-bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_18CrossRef

21.

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

22.

Kusaka, T., et al.: Solving 114-bit ECDLP for a barreto-naehrig curve. In: Kim, H., Kim, D.-C. (eds.) ICISC 2017. LNCS, vol. 10779, pp. 231–244. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78556-1_13CrossRef

23.

Menezes, A.J., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39(5), 1639–1646 (1993)MathSciNetCrossRef

24.

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_31CrossRef

25.

Petit, C., Kosters, M., Messeng, A.: Algebraic approaches for the elliptic curve discrete logarithm problem over prime fields. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9615, pp. 3–18. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49387-8_1CrossRef

26.

Pollard, J.M.: Monte Carlo methods for index computation (mod \(p\)). Math. Comput. 32(143), 918–924 (1978)

27.

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRef

28.

Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. Sancti Pauli 47(1), 81–92 (1998)MathSciNetMATH

29.

Semaev, I.A.: Evaluation of discrete logarithms in a group of \(p\)-torsion points of an elliptic curve in characteristic \(p\). Math. Comput. 67(221), 353–356 (1998)

30.

Semaev, I.A.: Summation polynomials and the discrete logarithm problem on elliptic curves. IACR Cryptology ePrint Archive 2004/031 (2004)

31.

Semaev, I.A.: New algorithm for the discrete logarithm problem on elliptic curves. IACR Cryptology eprint Archive 2015/310 (2015)

32.

Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of Symposium of Pure Mathematics, vol. 20, pp. 41–440 (1971)

33.

Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106, 2nd edn. Springer, New York (2009). https://doi.org/10.1007/978-0-387-09494-6CrossRefMATH

34.

Smart, N.P.: The discrete logarithm problem on elliptic curves of trace one. J. Cryptol. 12(3), 193–196 (1999)MathSciNetCrossRef

35.

Wenger, E., Wolfger, P.: Solving the discrete logarithm of a 113-bit Koblitz curve with an FPGA cluster. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 363–379. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_22CrossRef

36.

Yasuda, M., Shimoyama, T., Kogure, J., Izu, T.: Computational hardness of IFP and ECDLP. Appl. Algebra Eng. Commun. Comput. 27(6), 493–521 (2016)MathSciNetCrossRef

37.

Yokota, Y., Kudo, M., Yasuda, M.: Practical limit of index calculus algorithms for ECDLP over prime fields. In: International Workshop on Coding and Cryptography-WCC 2017 (2017). http://wcc2017.suai.ru/proceedings.html

Titel: Acceleration of Index Calculus for Solving ECDLP over Prime Fields and Its Limitation
verfasst von: Momonari Kudo
Yuki Yokota
Yasushi Takahashi
Masaya Yasuda
Verlag: Springer International Publishing
Buch: Cryptology and Network Security
Print ISBN: 978-3-030-00433-0

Electronic ISBN: 978-3-030-00434-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-00434-7_19

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"