XSL Attack - Solving Multivariate Quadratic Equations

Solving Multivariate Quadratic Equations

Solving 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 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, 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 monomials of a certain 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).