Abstract
The “XL-algorithm” is a computational method to solve overdetermined systems of polynomial equations which is based on a generalization of the well-known method of linearization; it was introduced to cryptology at Eurocrypt 2000.
In this paper, we prove upper bounds on the dimensions of the spaces of equations in the XL-algorithm. These upper bounds provide strong evidence that for any fixed finite field K and any fixed c εℕ the median of the running times of the original XL-algorithm applied to systems of m = n + c quadratic equations in n variables over K which have a solution in K is not subexponential in n. In contrast to this, in the introduction of the original paper on XL, the authors claimed to “provide strong theoretical and practical evidence that the expected running time of this technique is [...] subexponential if m exceeds n by a small number”.
More precise upper bounds on the dimensions of the spaces of equations in the XL-algorithm can be obtained if one assumes a standard conjecture from commutative algebra. We state the conjecture and discuss implications on the XL-algorithm.
Chapter PDF
Similar content being viewed by others
Keywords
References
Atiyah, M., Macdonald, I.: Introduction to Commutative Algebra. Addison-Wesley, Reading (1969)
Bardet, M., Faugère, J.-C., Salvy, B.: Complexity of Gröbner basis computations for Semi-regular Overdetermined sequences over \(\mathbb{F}_2\) with solutions in \(\mathbb{F}_2\). INRIA Rapport de recherche No. 5049 (2003)
Chen, J.-M., Yang, B.-Y.: All in the XL Familiy: Theory and Practice (June 2004) (manuscript)
Chen, J.-M., Yang, B.-Y.: Theoretical Analysis of XL over Small Fields. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 277–288. Springer, Heidelberg (2004)
Courtois, N.: Higher Order Correlation Attacks, XL algorithm, and Cryptanalysis of Toyocrypt. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182–199. Springer, Heidelberg (2003)
Courtois, N., Klimov, A., Pararin, J., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations (extended version) (August 24, 2004), Available under, http://www.minrank.org/xlfull.pdf
Courtois, N., Klimov, A., Pararin, 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)
Courtois, N., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)
Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Springer, New York (1995)
Fröberg, R.: An inequality for Hilbert series of graded algebras. Math. Scand. 56, 117–144 (1985)
Knuth, D.: The Art of Computer Programming. Addison-Wesley, Reading (1973)
Matsumura, H.: Commutative Ring Theory. Cambridge University Press, Cambridge (1986)
Moh, T.: On the method of ”XL” and its inefficiency to TTM. (manuscript) (January 28, 2000), Available under, http://eprint.iacr.org/2001/047
Murphy, S., Robshaw, M.J.B.: Essential algebraic structure within the AES. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 1–16. Springer, Heidelberg (2002)
Pardue, K.: Generic Sequences of Polynomials (manuscript ) (March 30, 2000)
Valla, G.: Problems and Results on Hilbert Polynomials of Graded Algebras. In: Elías, J., Giral, J. (eds.) Six Lectures on Commutative Algebra. Progress in Mathematics, vol. 166. Birkhäuser, Basel (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Diem, C. (2004). The XL-Algorithm and a Conjecture from Commutative Algebra. In: Lee, P.J. (eds) Advances in Cryptology - ASIACRYPT 2004. ASIACRYPT 2004. Lecture Notes in Computer Science, vol 3329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30539-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-30539-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23975-8
Online ISBN: 978-3-540-30539-2
eBook Packages: Springer Book Archive