An Analysis of the Compact XSL Attack on BES and Embedded SMS4

Date Added: Aug 2009
Format: PDF

The eXtended Sparse Linearization method, introduced in 2002 by Courtois and Pieprzyk, is a refinement of the XL algorithm and is supposed to work on special types of ciphers such as AES. One main improvement is to take advantage of the sparseness of the multivariate quadratic system of the cipher: the equations should only be multiplied by "Carefully selected monomials" so as to generate a new system where there are more equations than monomials. This will allow the new equations to be solved via linearization.