Paper 2010/596

Solving Systems of Multivariate Quadratic Equations over Finite Fields or: From Relinearization to MutantXL

Enrico Thomae and Christopher Wolf

Abstract

In this article we investigate algorithms for solving non-linear multivariate equations over finite fields and the relation between them. For non binary fields usually computing the Gröbner basis of the corresponding ideal is the best choice in this context. One class of algorithms is based on Buchberger's algorithm. Today's best algorithms like F_4 and F_5 belong to this class. Another strategy to solve such systems is called eXtended Linearization (XL) from Eurocrypt 2000. In the past both strategies were treated as different ideas and there was a heated discussion which of them to prefer. Since Ars et al. proved in 2004 that XL is a redundant version of F_4, the latter seemed to be the winner. But that was not the end of the line as piece for piece the idea emerged that both classes are only different views on the same problem. We even think that they are just different time-memory optimizations. One indication to that can be found in the PhD of Albrecht, who introduced MatrixF_5, a F_5 version of XL. A second indication can be found in the PhD of Mohamed, who introduced a memory-friendly version of XL using Wiedemanns algorithm. We want to give further evidence by providing a theoretical analysis of MutantXL. We show that MutantXL solves at the same degree of regularity as its competitors F_4 and F_5 for most instances. Thereby we also confirm recent results of Albrecht, who showed that MutantXL is a redundant version of F_4, i.e. it never solves below the degree of regularity. We show that MutantXL has, compared to WiedemannXL, to pay its gain in efficiency with memory. To enhance the understanding of the whole XL-family of algorithms we give a full overview from Relinearization over XL to MutantXL and provide some additional theoretical insights.

Note: Pdf file was damaged. It was not possible to search within the file.