Abdelmageed Mohamed, Wael Said
Improvements for the XL Algorithm with Applications to Algebraic Cryptanalysis.
TU Darmstadt, Darmstadt, Germany
[Ph.D. Thesis], (2011)
Available under Creative Commons Attribution Non-commercial No Derivatives.
Download (1063Kb) | Preview
|Item Type:||Ph.D. Thesis|
|Title:||Improvements for the XL Algorithm with Applications to Algebraic Cryptanalysis|
The problem of solving systems of multivariate polynomial equations over finite fields is a classical and fundamental problem in symbolic computation. This problem has important applications in numerous domains. In cryptography, the security of multivariate-based public-key cryptosystems relies on the difficulty of solving systems of multivariate quadratic polynomial equations over finite fields.
Several algorithms have been proposed to find solution(s) for systems of multivariate polynomial equations over finite fields. In 2000, the XL algorithm was introduced as a tool for solving such systems. The overall performance of XL depends on the degree at which a solution could be found. From a practical point of view, the running time and memory consumption for XL is greater than consumptions of the F4 algorithm, the best known efficient algorithm for solving systems of polynomial equations. The main purpose of this thesis is to improve the XL algorithm and test the suggested improvements with applications to algebraic cryptanalysis.
One way to improve the XL algorithm is to generate new low degree polynomials that are in the ideal generated by the original polynomials. The hope is that these new polynomials are linearly independent from the ones already generated by XL, so that the degree at which XL has the ability to solve a system could be minimized. These low degree polynomials are discovered and named mutants by Jintai Ding.
Basically, the use of these mutants is the first improvement that is suggested in the thesis at hand. This improvement is the MutantXL algorithm and its implementation. An improvement of MutantXL, called MXL2, is also presented in this thesis. MXL2 uses two substantial improvements over GF(2) that oftentimes allow to solve systems with significantly smaller matrix sizes than XL and MutantXL. The use of MXL2 in the context of algebraic cryptanalysis is demonstrated by breaking two multivariate-based public-key cryptosystems, namely Little Dragon Two and Poly-Dragon, more efficiently than F4.
The second improvement is related to the structure of matrices generated by XL. These matrices tend to be sparse. Therefore, transforming such matrices to the row echelon form using Gaussian elimination makes the linear algebra cost so much in terms of memory and time due to the fill-in property. The use of the Wiedemann algorithm as a solver instead of Gaussian elimination over GF(256) with a scalar version of the Wiedemann algorithm was introduced by Bo-Yin Yang et al. In this thesis, we represent the use and combination of the block Wiedemann algorithm over GF(2) and XL, referred to as WXL algorithm. One way to improve WXL is to use more than one processor based on the advantage that the Wiedemann algorithm is able to be parallelized. By using PWXL, a parallelized version of WXL, systems with higher number of variables can be solved. These systems were not solved before by any other algebraic solver. In particular, PWXL can successfully solve instances of the HFE cryptosystem over GF(2) that have the same univariate degree as the HFE challenge-2 with 37 quadratic equations in 37 variables using 81 processors in 7.5 days.
The combination of the two suggested improvements for the XL algorithm, the mutant strategy and the parallelized Wiedemann algorithm, is the third improvement. The first part of this improvement is the generation of mutants by using the matrix kernel which also could be computed by the Wiedemann algorithm. The second part is to use mutants that are generated by Wiedemann algorithm. Generating mutants using the Wiedemann algorithm then solving using MutantXL is the first scenario to use such mutants. The second scenario is the use of the WMXL algorithm which is a combination of the PWXL algorithm and the concept of a mutant in order to obtain a solution in an efficient way for structured systems.
Effective and efficient improvements for the XL algorithm are presented. These improvements are based on the concept of a mutant and the parallelized Wiedemann algorithm. The importance of these improvements is indicated by solving systems of multivariate polynomial equations arising from cryptography. Therefore, designers of new cryptosystems should take care about these new suggested algorithms.
|Place of Publication:||Darmstadt, Germany|
|Classification DDC:||000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik|
|Divisions:||Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra|
|Date Deposited:||16 Jun 2011 11:00|
|Last Modified:||07 Dec 2012 12:00|
|License:||Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0|
|Referees:||Buchmann, Prof. Dr. Johannes and Ding, Prof. Dr. Jintai|
|Refereed:||6 June 2011|
Actions (login required)