Editing XSL attack (section)

==Solving multivariate quadratic equations==
Solving [[Polynomial#Classifications|multivariate]] quadratic equations (MQ) over a finite set of numbers is an [[NP-hard]] problem (in the general case) with several applications in cryptography. The XSL attack requires an efficient algorithm for tackling MQ. In 1999, Kipnis and [[Adi Shamir|Shamir]] showed that a particular [[public key algorithm]], known as the [[Hidden Field Equations]] scheme (HFE), could be reduced to an [[overdetermined system]] of quadratic equations (more equations than unknowns). One technique for solving such systems is [[linearization (algebra)|linearization]], which involves replacing each quadratic term with an independent variable and solving the resultant linear system using an algorithm such as [[Gaussian elimination]]. To succeed, linearization requires enough [[linearly independent]] equations (approximately as many as the number of terms). However, for the cryptanalysis of HFE there were too few equations, so Kipnis and Shamir proposed ''re-linearization'', a technique where extra non-linear equations are added after linearization, and the resultant system is solved by a second application of linearization. Re-linearization proved general enough to be applicable to other schemes.

In 2000, Courtois et al. proposed an improved algorithm for MQ known as ''XL'' (for ''eXtended Linearization''), which increases the number of equations by multiplying them with all [[monomial]]s of a certain [[Degree of a monomial|degree]]. Complexity estimates showed that the XL attack would not work against the equations derived from block ciphers such as AES. However, the systems of equations produced had a special structure, and the XSL algorithm was developed as a refinement of XL which could take advantage of this structure. In XSL, the equations are multiplied only by carefully selected monomials, and several variants have been proposed.

Research into the efficiency of XL and its derivative algorithms remains ongoing (Yang and Chen, 2004).