Huang, Ming-Deh; Kosters, Michiel; Petit, Christophe; Yeo, Sze Ling; Yun, Yang Quasi-subfield polynomials and the elliptic curve discrete logarithm problem. (English) Zbl 1450.94036 J. Math. Cryptol. 14, 25-38 (2020). Let \(q\) be a prime and \(K = \mathbb F_q^n\) be a finite field with \(q^n\) elements. In this paper a new class of polynomials of \(K[X]\) is introduced, called {\em quasi-subfield polynomials.} They have the form \(X^{q^{n^{\prime}}}-\lambda(X)\) with \(\log_q(\deg \lambda) < n^{\prime}/2\) and divide \( X^{q^n} -X \). These polynomials are used for the construction of a polynomial system over the field \(K\) such that its zero set gives a relation for the index calculus method. By applying Rojas’s algorithm to solve this polynomial system, precise complexity results for the index calculus algorithm are given. When \(\deg \lambda\) is small enough, it is shown that such polynomials could lead to faster algorithms for the elliptic curve discrete logarithm problem (ECDLP). The existence of these polynomials is investigated and a particular family is provided leading to an ECDLP algorithm more efficient than exhaustive search. Reviewer: Dimitros Poulakis (Thessaloniki) Cited in 4 Documents MSC: 94A60 Cryptography 11T06 Polynomials over finite fields 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) Keywords:elliptic curve discrete logarithm problem; cryptanalysis; finite fields; index calculus algorithm PDFBibTeX XMLCite \textit{M.-D. Huang} et al., J. Math. Cryptol. 14, 25--38 (2020; Zbl 1450.94036) Full Text: DOI References: [1] Leonard M. Adleman, A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography (Abstract), in: FOCS, pp. 55-60, IEEE, 1979. [2] Razvan Barbulescu, Pierrick Gaudry, Antoine Joux and Emmanuel Thomé, A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic, in: Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Tech- niques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, pp. 1-16, 2014. · Zbl 1326.11080 [3] E. R. Berlekamp, Algebraic coding theory, Aegean Park Press, Laguna Hills, CA, USA, 1984. · Zbl 1320.94002 [4] Claus Diem, On the discrete logarithm problem in elliptic curves, Compositio Math- ematica147 (2011), 75-104. · Zbl 1213.11200 [5] Whitfield Diffie and Martin E. Hellman, New Directions in Cryptography, IT-22 (1976), 644-654. · Zbl 0435.94018 [6] Jintai Ding and Timothy J. Hodges, Inverting HFE Systems Is Quasi-Polynomial for All Fields, in: CRYPTO (Phillip Rogaway, ed.), Lecture Notes in Computer Science 6841, pp. 724-742, Springer, 2011. · Zbl 1287.94064 [7] Vivien Dubois and Nicolas Gama, The Degree of Regularity of HFE Systems, in: ASIACRYPT (Masayuki Abe, ed.), Lecture Notes in Computer Science 6477, pp. 557-576, Springer, 2010. · Zbl 1290.94066 [8] Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases (F4)., Journal of Pure and Applied Algebra139 (1999), 61-88. · Zbl 0930.68174 [9] Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases with- out reduction to zero (F5), in: Proceedings of the 2002 international symposium on Symbolic and algebraic computation, ISSAC ‘02, pp. 75-83, ACM, New York, NY, USA, 2002. · Zbl 1072.68664 [10] Jean-Charles Faugère and Antoine Joux, Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases, in: CRYPTO (Dan Boneh, ed.), Lecture Notes in Computer Science 2729, pp. 44-60, Springer, 2003. · Zbl 1122.94371 [11] Jean-Charles Faugère, Ludovic Perret, Christophe Petit and Guénaël Renault, Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields, in: EUROCRYPT (David Pointcheval and Thomas Johansson, eds.), Lecture Notes in Computer Science 7237, pp. 27-44, Springer, 2012. · Zbl 1290.94070 [12] Steven D. Galbraith and Shishay W. Gebregiyorgis, Summation Polynomial Algo- rithms for Elliptic Curves in Characteristic Two, in: Progress in Cryptology -IN- DOCRYPT 2014 - 15th International Conference on Cryptology in India, New Delhi, India, December 14-17, 2014, Proceedings (Willi Meier and Debdeep Mukhopad- hyay, eds.), Lecture Notes in Computer Science 8885, pp. 409-427, Springer, 2014. · Zbl 1337.94036 [13] P. Gaudry, E. Thomé, N. Thériault and C. Diem, A double large prime variation for small genus hyperelliptic index calculus, Math. Comp. 76 (2007), 475-492 (elec- tronic). · Zbl 1179.94062 [14] Pierrick Gaudry, Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symb. Comput. 44 (2009), 1690-1702. · Zbl 1177.94148 [15] Louis Granboulan, Antoine Joux and Jacques Stern, Inverting HFE Is Quasipolynomial, in: CRYPTO (Cynthia Dwork, ed.), Lecture Notes in Computer Science 4117, pp. 345-356, Springer, 2006. · Zbl 1161.94400 [16] Ming-Deh A. Huang, Michiel Kosters and Sze Ling Yeo, Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP, in: Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, pp. 581-600, 2015. · Zbl 1375.94135 [17] Yun-Ju Huang, Christophe Petit, Naoyuki Shinohara and Tsuyoshi Takagi, Improvement of Faugère et al.’s Method to Solve ECDLP, in: IWSEC (Kazuo Sakiyama and Masayuki Terada, eds.), Lecture Notes in Computer Science 8231, pp. 115-132, Springer, 2013. · Zbl 1357.94069 [18] Antoine Joux and Vanessa Vitse, Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on E(𝔽_q^5), Cryptology ePrint Archive, Report 2010/157. To appear in Journal of Cryptology., 2010, http://eprint.iacr.org/. · Zbl 1291.94107 [19] Christophe Petit, Bounding HFE with SRA, https://www.cs.bham.ac.uk/ petitcz/files/SRA_GB.pdf. [20] Christophe Petit, Michiel Kosters and Ange Messeng, Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields, in: Public-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II (Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano and Bo-Yin Yang, eds.), Lecture Notes in Computer Science 9615, pp. 3-18, Springer, 2016 · Zbl 1353.94069 [21] Christophe Petit and Jean-Jacques Quisquater, On Polynomial Systems Arising from a Weil Descent, in: Asiacrypt (Xiaoyun Wang and Kazue Sako, eds.), Lecture Notes in Computer Science 7658, pp. 451-466, Springer, 2012. · Zbl 1292.94127 [22] Maurice Rojas, Solving Degenerate Sparse Polynomial Systems Faster, Journal of Symbolic Computation28 (1999), 155-186. · Zbl 0943.65060 [23] Igor Semaev, Summation polynomials and the discrete logarithm problem on elliptic curves, Cryptology ePrint Archive, Report 2004/031, 2004, http://eprint.iacr.org/. [24] Michael Shantz and Edlyn Teske, Solving the Elliptic Curve Discrete Logarithm Problem Using Semaev Polynomials, Weil Descent and Grb̈ner Basis Methods - An Experimental Study, in: Number Theory and Cryptography - Papers in Honor of Johannes Buchmann on the Occasion of His 60th Birthday, pp. 94-107, 2013. · Zbl 1320.11125 [25] Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Information Theory32 (1986), 54-62. · Zbl 0607.65015 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.