# Proof of correctness of the XL-algorithm for polynomial systems

Section 12.4 of G.V. Bard's Algebraic Cryptanalysis discusses the XL-algorithm (first reported by N.T. Courtois and A. Shamir in Efficient algorithms for solving overdefined systems of multivariate polynomial equations and Courtois' thesis).

The technique is based on the following. Say we have a system of polynomial equations such as:

$$1+x+y+z+wz+yz = 0\\ x+z+wx+wy+wz+xy+xz+yz=1\\ w+y+wx+xz+yz=0\\ x+wx+wy+wz+yz=1\\$$

This is the example in Bard's book and I am guessing we are in $GF(2)$. The system is clearly underdetermined. The algorithm says that you should enhance the degree of the equation from $d$ to $D>d$ (usually $D=d+1$ or $D=d+2$) and make a list $L$ of monomials of degree $D-d$ or less starting with the monomial $1$ of degree $0$. You then take those monomials and multiply them by the above system and solve the linearized system.

The resulting system has $m\lvert L\rvert$ where $m$ was the initial number of equations.

Is there a proof of correctness of the method? Is there a simple way to prove that it is correct mathematically?

• Yes, we are in $GF(2)$ (at least typically that is the case in the cryptographic applications where XL is considered). I don't know if there is any proof of correctness. To help you understand XL, it might help to first learn about relinearization, since XL in some sense builds on those ideas. See, e.g., crypto.stackexchange.com/a/3736/351. In cryptography, normally XL is used in cases where the system is fully determined (e.g., more equations than unknowns) but its linearization is underdetermined (more unique monomials than equations). – D.W. Jun 9 '14 at 19:45