About the XL algorithm over GF(2). (English) Zbl 1039.94511
Joye, Marc (ed.), Topics in cryptology – CT-RSA 2003. The cryptographers’ track at the RSA conference 2003, San Francisco, CA, USA, April 13–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-00847-0/pbk). Lect. Notes Comput. Sci. 2612, 141-157 (2003).
Summary: Several public key cryptosystems (HFE, Quartz, Sflash, etc.) are based on the problem MQ of solving a system of multivariate quadratic equations over a finite field. At Asiacrypt 2002, N. Courtois and J. Pieprzyk [Lect. Notes Comput. Sci. 2501, 267–287 (2002; Zbl 1065.94543)] showed that the MQ problem is also relevant to the security of AES.
At Eurocrypt 2000, N. Courtois, A. Klimov, J. Patarin and A. Shamir [Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Lect. Notes Comput. Sci. 1807, 392–407 (2000)] introduced the XL algorithm for solving MQ. They showed that if the number of equations \(m\) is much larger than the number of variables \(n \), such overdefined MQ systems can be easily solved. From their simplified and heuristic analysis it seemed that even when \(m=n\), a variant of XL could still be subexponential. The exact complexity of the XL algorithm remained an open problem. Moreover, all their simulations has been done over GF(127) and with \(D<127\), with \(D\) being the parameter of the XL algorithm.
At Asiacrypt 2002, the algorithm XSL, derived from XL, was introduced for the cryptanalysis of block ciphers [Courtois and Pieprzyk, loc. cit.]. Very little is known about the behaviour of XSL, and we believe that one should study the XL algorithm itself first. In this paper we study the behaviour of XL for systems of quadratic equations over GF(2). We show that the possibility to use the equations \(x_i^2=x_i\) of the field GF(2), which are also quadratic, makes the XL algorithm work better. We also introduce two improved versions of XL, called XL’ and XL2, with an improved final step of the algorithm (that also can be used in XSL). We present an explanation for the linear dependencies that appear in the XL algorithm, and derive a formula for the number of linearly independent equations in XL or XL2. Then we run various computer simulations and observe that this formula is always verified. Apparently we are able to predict exactly the behaviour of XL, XL’ and XL2 for random systems of equations. Due to the entanglement of linear dependencies, the analysis of XL becomes increasingly difficult, and XL may be really exponential for \(m=n\).
For the entire collection see [Zbl 1017.00055].
At Eurocrypt 2000, N. Courtois, A. Klimov, J. Patarin and A. Shamir [Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Lect. Notes Comput. Sci. 1807, 392–407 (2000)] introduced the XL algorithm for solving MQ. They showed that if the number of equations \(m\) is much larger than the number of variables \(n \), such overdefined MQ systems can be easily solved. From their simplified and heuristic analysis it seemed that even when \(m=n\), a variant of XL could still be subexponential. The exact complexity of the XL algorithm remained an open problem. Moreover, all their simulations has been done over GF(127) and with \(D<127\), with \(D\) being the parameter of the XL algorithm.
At Asiacrypt 2002, the algorithm XSL, derived from XL, was introduced for the cryptanalysis of block ciphers [Courtois and Pieprzyk, loc. cit.]. Very little is known about the behaviour of XSL, and we believe that one should study the XL algorithm itself first. In this paper we study the behaviour of XL for systems of quadratic equations over GF(2). We show that the possibility to use the equations \(x_i^2=x_i\) of the field GF(2), which are also quadratic, makes the XL algorithm work better. We also introduce two improved versions of XL, called XL’ and XL2, with an improved final step of the algorithm (that also can be used in XSL). We present an explanation for the linear dependencies that appear in the XL algorithm, and derive a formula for the number of linearly independent equations in XL or XL2. Then we run various computer simulations and observe that this formula is always verified. Apparently we are able to predict exactly the behaviour of XL, XL’ and XL2 for random systems of equations. Due to the entanglement of linear dependencies, the analysis of XL becomes increasingly difficult, and XL may be really exponential for \(m=n\).
For the entire collection see [Zbl 1017.00055].
MSC:
| 94A60 | Cryptography |
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
