Improved Strategies for Solving Multivariate Polynomial Equation Systems over Finite Fields

One of the important research problems in cryptography is the problem of solving multivariate polynomial equations over finite fields. The hardness of solving this problem is the measure of the security of many public key cryptosystems as well as of many symmetric cryptosystems, like block and stream ciphers. In recent years, algebraic cryptanalysis has been presented as a method of attacking cryptosystems. This method consists in solving multivariate polynomial systems. Therefore, developing algorithms for solving such systems is a hot research topic. Over the recent years, several algorithms have been proposed to solve multivariate polynomial systems over finite fields. A very promising type of these algorithms is based on enlarging a system by generating additional equations and using linear algebra techniques to obtain a solution. Theoretical complexity estimates have shown that algebraic attacks made using these algorithms are infeasible for many realistic applications. This is due to the fact that, in many practical cases, the computations made by these algorithms require a lot of time and memory resources. A big challenge is to improve this algorithm in order to be able to use the limited available memory and time resources to solve large multivariate polynomial systems which exist in practice. In this thesis we propose strategies to improve the enlargement step of these algorithms. We apply these strategies to the well studied XL algorithm, due to its simple structure, and show that combining these strategies with XL makes it highly competitive to the state-of-the-art algorithms. In 2006, Jintai Ding presented the concept of mutant polynomials . Mutants are polynomials of a lower degree than expected that appear during the linear algebra step of XL. The MutantXL algorithm presented in this thesis uses the concept of mutants to improve the solving process of the XL algorithm. The MXL2 algorithm is introduced as an improved version of the MutantXL algorithm by developing a partial enlargement strategy. Specifically, we modify MutantXL in a way such that when it enlarges the system, it partitions the set of polynomials of the maximal degree D into some subsets using a special criteria. After that it explores this set of polynomials, one subset at a time, without being forced to store the whole set at once. This results in solving systems with fewer number of enlarged polynomials than MutantXL. The main drawback of MXL2, as well as XL and MutantXL algorithms, is that it can solve only systems having a unique solution. In order to solve systems with a finite number of solutions, we present a new sufficient condition for a set of polynomials to be a Gröbner basis . We used this new condition as a termination criteria for the MXL2 algorithm. This modification together with further improvements to the enlargement step of MXL2 are introduced in the MXL3 algorithm for computing Gröbner bases. This thesis also introduces the MGB algorithm which uses a flexible partial enlargement strategy to provide an important improvement to MXL3. The preliminary study presented at the end of the thesis suggests a new upper bound for the complexity of computing Gröbner bases which motivates thinking of new paradigms for estimating the complexity of Gröbner bases computation. The results in this thesis show that the proposed strategies dramatically improve the performance of the XL algorithm and, moreover, introduce algorithms that outperform Magma’s implementation of F4, one of the currently most efficient algorithms, in terms of time and memory consumption in many cases. Moreover, an adapted version of MutantXL is used to attack the MQQ cryptosystem faster and uses less memory than attacks using F4