Abstract
In the last two decades, many computational problems arising in cryptography have been successfully reduced to various systems of polynomial equations. In this paper, we revisit a class of polynomial systems introduced by Faugère, Perret, Petit and Renault. Based on new experimental results and heuristic evidence, we conjecture that their degrees of regularity are only slightly larger than the original degrees of the equations, resulting in a very low complexity compared to generic systems. We then revisit the application of these systems to the elliptic curve discrete logarithm problem (ECDLP) for binary curves. Our heuristic analysis suggests that an index calculus variant due to Diem requires a subexponential number of bit operations \((O2^{c\,n^{2/3}\log n})\) over the binary field \({\mathbb F}{2^n}\), where c is a constant smaller than 2. According to our estimations, generic discrete logarithm methods are outperformed for any n > N where N ≈ 2000, but elliptic curves of currently recommended key sizes (n ≈ 160) are not immediately threatened. The analysis can be easily generalized to other extension fields.
Chapter PDF
Similar content being viewed by others
References
Leonard, M.A.: A subexponential algorithm for the discrete logarithm problem with applications to cryptography (abstract). In: FOCS, pp. 55–60. IEEE (1979)
Leonard, M.A.: The function field sieve. In: Adleman, Huang [4], pp. 108–121
Leonard, M.A., DeMarrais, J., Huang, M.-D.A.: A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. In: Adleman, Huang, [4] pp. 28–40
Huang, M.-D.A., Adleman, L.M. (eds.): ANTS 1994. LNCS, vol. 877. Springer, Heidelberg (1994)
Adleman, L.M., Huang, M.-D.A.: Function field sieve method for discrete logarithms over finite fields. Inf. Comput. 151(1-2), 5–16 (1999)
Bardet, M.: Etude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. PhD thesis, Université Paris 6 (2004)
Bardet, M., Faugère, J.-C., Salvy, B.: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In: International Conference on Polynomial System Solving, ICPSS, pp. 71–75 (November 2004)
Bardet, M., Faugère, J.-C., Salvy, B.: Asymptotic expansion of the degree of regularity for semi-regular systems of equations. In: Gianni, P. (ed.) The Effective Methods in Algebraic Geometry Conference, Mega 2005, pp. 1–14 (May 2005)
Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology 3(3), 177–197 (2010)
Bettale, L., Faugère, J.-C., Perret, L.: Cryptanalysis of multivariate and odd-characteristic hfe variants. In: Catalano, et al. [14], pp. 441–458
Bettale, L., Faugère, J.-C., Perret, L.: Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic. Des. Codes Cryptography, 1–42 (accepted, 2012)
Bouillaguet, C., Faugère, J.-C., Fouque, P.-A., Perret, L.: Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem. In: Catalano, et al. [14], pp. 473–493
Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Universität Innsbruck (1965)
Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.): PKC 2011. LNCS, vol. 6571, pp. 2011–2014. Springer, Heidelberg (2011)
Collins, G.: The calculation of multivariate polynomial resultants. Journal of the Association for Computing Machinery 18, 515–522 (1971)
Coppersmith, D.: Fast evaluation of logarithms in fields of characteristic two. IEEE Transactions on Information Theory 30(4), 587–593 (1984)
Courtois, N.T.: The Security of Hidden Field Equations (HFE). In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 266–281. Springer, Heidelberg (2001)
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms, 1st edn. Springer, Heidelberg (1992)
Diem, C.: On the discrete logarithm problem in elliptic curves. Compositio Mathematica 147, 75–104 (2011)
Diem, C.: On the discrete logarithm problem in elliptic curves II (2011), http://www.math.uni-leipzig.de/~diem/preprints/dlp-ell-curves-II.pdf
Ding, J., Hodges, T.J.: Inverting HFE Systems Is Quasi-Polynomial for All Fields. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 724–742. Springer, Heidelberg (2011)
Ding, J., Kleinjung, T.: Degree of regularity for HFE-. IACR Cryptology ePrint Archiv, 2011:570 (2011)
Dubois, V., Gama, N.: The Degree of Regularity of HFE Systems. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 557–576. Springer, Heidelberg (2010)
Enge, A., Gaudry, P.: A general framework for subexponential discrete logarithm algorithms. Acta Arith. 102(1), 83–103 (2002)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139(1-3), 61–88 (1999)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 75–83. ACM, New York (2002)
Faugère, J.-C., Din, M.S.E., Spaenlehauer, P.-J.: Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology. In: ISSAC, pp. 257–264 (2010)
Faugère, J.-C., Din, M.S.E., Spaenlehauer, P.-J.: Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity. J. Symb. Comput. 46(4), 406–437 (2011)
Faugère, J.-C., Joux, A.: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)
Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic Cryptanalysis of McEliece Variants with Compact Keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010)
Faugère, J.-C., Perret, L.: Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 30–47. Springer, Heidelberg (2006)
Faugère, J.-C., Perret, L., Petit, C., Renault, G.: New subexponential algorithms for factoring in \(SL(2,{\mathbb F}_{2^n})\). Cryptology ePrint Archive, Report 2011/598 (2011), http://eprint.iacr.org/
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, Johansson [50], pp. 27–44
Gaudry, P., Thomé, E., Thériault, N., Diem, C.: A double large prime variation for small genus hyperelliptic index calculus. Math. Comp. 76(257), 475–492 (electronic) (2007)
Gaudry, P.: An Algorithm for Solving the Discrete Log Problem on Hyperelliptic Curves. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 19–34. Springer, Heidelberg (2000)
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)
Granboulan, L., Joux, A., Stern, J.: Inverting HFE Is Quasipolynomial. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 345–356. Springer, Heidelberg (2006)
Joux, A., Lercier, R.: The Function Field Sieve in the Medium Prime Case. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 254–270. Springer, Heidelberg (2006)
Joux, A., Vitse, V.: Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on \(E(\mathbb{F}_{q^5})\). Cryptology ePrint Archive, Report 2010/157. Journal of Cryptology (2010), http://eprint.iacr.org/
Joux, A., Vitse, V.: Cover and decomposition index calculus on elliptic curves made practical - application to a previously unreachable curve over \(\mathbb{F}_{p^6}\). In: Pointcheval, Johansson [50], pp. 9–26
Kipnis, A., Shamir, A.: Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999)
Kraitchik, M.: Théorie des nombres. Gauthier-Villars (1922)
Lazard, D.: Gröbner-Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations. In: van Hulzen, J.A. (ed.) ISSAC 1983 and EUROCAL 1983. LNCS, vol. 162, pp. 146–156. Springer, Heidelberg (1983)
Macaulay, F.S.: The algebraic theory of modular systems. Cambridge Mathematical Library, vol. XXXI. Cambridge University Press (1916)
Macaulay, F.S.: Some properties of enumeration in the theory of modular systems. Proc. London Math. Soc. 26, 531–555 (1927)
National Institute of Standards and Technology. Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186-3 (2009)
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Petit, C., Quisquater, J.-J.: On polynomial systems arising from a weil descent. Cryptology ePrint Archive, Report 2012/146 (2012), http://eprint.iacr.org/
Pointcheval, D., Johansson, T. (eds.): EUROCRYPT 2012. LNCS, vol. 7237, pp. 2012–2031. Springer, Heidelberg (2012)
Semaev, I.: Summation polynomials and the discrete logarithm problem on elliptic curves (2004), http://www.isg.rhul.ac.uk/~ppai034/_pub/papers/Semaev%20%28Feb%29.pdf
Yang, B.-Y., Chen, J.-M., Courtois, N.T.: On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 401–413. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research
About this paper
Cite this paper
Petit, C., Quisquater, JJ. (2012). On Polynomial Systems Arising from a Weil Descent. In: Wang, X., Sako, K. (eds) Advances in Cryptology – ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34961-4_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-34961-4_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34960-7
Online ISBN: 978-3-642-34961-4
eBook Packages: Computer ScienceComputer Science (R0)