TU Darmstadt / ULB / TUprints

Improvements for the XL Algorithm with Applications to Algebraic Cryptanalysis

Abdelmageed Mohamed, Wael Said (2011)
Improvements for the XL Algorithm with Applications to Algebraic Cryptanalysis.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
WST_Diss.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Improvements for the XL Algorithm with Applications to Algebraic Cryptanalysis
Language: English
Referees: Buchmann, Prof. Dr. Johannes ; Ding, Prof. Dr. Jintai
Date: 13 June 2011
Place of Publication: Darmstadt
Date of oral examination: 6 June 2011
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage

Das Lösen von Systemen multivariater Polynomgleichungen über endlichen Körpern ist ein klassisches und fundamentales Problem. Dieses Problem hat wichtige Anwendungen in verschiedenen Gebieten. In der Kryptographie beruht die Sicherheit multivariater Public-Key-Kryptosysteme auf der Schwierigkeit, Systeme multivariater quadratischer Polynomgleichungen über endlichen Körpern zu lösen.

In der Vergangenheit wurden mehrere Algorithmen zum Auffinden von Lösungen multivariater Polynomgleichungen über endlichen Körpern vorgeschlagen. Im Jahr 2000 wurde der XL Algorithmus als Werkzeug für das Lösen solcher Systeme eingeführt. Die Effizienz von XL hängt hauptsächlich von dem Grad ab, bei dem eine Lösung gefunden werden kann. In der Praxis sind Laufzeit und Speicherverbrauch des XL-Algorithmus größer als für den F4-Algorithmus, den besten bekannten Algorithmus für das Lösen von Systemen polynomialer Gleichungen. Der Hauptzweck dieser Arbeit ist es, den XL-Algorithmus zu verbessern und die vorgeschlagenen Verbesserungen an Anwendungen aus der algebraischen Kryptanalyse zu testen.

Eine Möglichkeit, den XL-Algorithmus zu verbessern, besteht darin, neue Polynome niedrigen Grades zu generieren, die im von den ursprünglichen Polynomen erzeugten Ideal liegen. Man hofft, dass diese neuen Polynome von den bestehenden linear unabhängig sind, so dass der Grad, bei dem XL das System lösen kann, minimiert werden kann. Diese Polynome kleinen Grades wurden von Jintai Ding entdeckt und als mutants bezeichnet. Im Prinzip ist die Verwendung dieser mutants die erste Verbesserung des XL Algorithmus, die in dieser Arbeit vorgeschlagen wird. Dies wird im MutantXL Algorithmus und seiner Implementierung erreicht. Eine weitere Verbesserung des MutantXL-Algorithmus namens MXL2 wird ebenfalls in dieser Arbeit beschrieben. MXL2 verwendet zwei wesentliche Verbesserungen über GF(2), die das Lösen von Systemen mit deutlich kleineren Matrizen erlauben als XL und MutantXL. MXL2 wird in dieser Arbeit im Rahmen der algebraischen Kryptanalyse benutzt, um zwei multivariate public-key Kryptosysteme zu brechen, nämlich Little Dragon Two und Poly Dragon.

Die zweite Verbesserung hängt mit der Struktur der von XL generierten Matrizen zusammen. Ab einem gewissen Grad tendieren diese Matrizen dazu, schwach besetzt zu sein. Deshalb ist es bezüglich Speicher und Zeit sehr kostspielig, diese Matrizen mit Gauss-Elimination auf Zeilenstufenform zu bringen. Die Verwendung des Wiedemann-Algorithmus anstatt der Gauss Elimination über GF(256) mit einer skalaren Version des Wiedemann-Algorithmus wurde von Bo-Ying Yang et al. eingeführt. In dieser Arbeit beschreiben wir den Gebrauch des blockweisen Wiedemann-Algorithmus über GF(2) und seine Kombination mit dem XL-Algorithmus, die wir als WXL bezeichnen. Eine Möglichkeit, den WXL Algorithmus zu verbessern, besteht darin, mehr als einen Prozessor zu verwenden. Man nutzt dabei die Tatsache aus, dass der Wiedemann-Algorithmus parallelisiert werden kann. Indem man PWXL, eine parallelisierte Version von WXL, benutzt, können Systeme mit einer größeren Zahl von Variablen gelöst werden. Diese Systeme wurden bisher von keinem anderen algebraischen Algorithmus gelöst. PWXL kann insbesondere Instanzen des HFE Kryptosystems mit 37 quadratischen Gleichungen in 37 Variablen über GF(2) lösen. Diese besitzen den gleichen univariaten Grad wie die von HFE Challenge-2 und können bei Benutzung von 81 Prozessoren in 7.5 Tagen erfolgreich gelöst werden.

Die Kombination der beiden vorgeschlagenen Verbesserungen, der mutant Strategie und des parallelisierten Wiedemann-Algorithmus, ist die dritte Verbesserung. Der erste Teil dieser Verbesserung ist das Erzeugen der mutants durch Benutzung des Kerns einer Matrix, der ebenfalls mit Hilfe des Wiedemann-Algorithmus erzeugt werden kann. Der zweite Teil besteht darin, die durch den Wiedemann-Algorithmus erzeugten mutants für das Lösen des Systems zu verwenden. Das Erzeugen von mutants durch Wiedemann und das Lösen mit MutantXL ist das erste Szenario für den Gebrauch solcher mutants. Das zweite Szenario ist die Verwendung des WMXL Algorithmus, der eine Kombination aus XL-Algorithmus, Wiedemann-Algorithmus und dem Konzept der mutants darstellt, um für strukturierte Systeme eine Lösung auf effektive Weise zu erhalten.

Es werden effiziente und wirksame Verbesserungen des XL-Algorithmus vorgestellt. Diese Verbesserungen basieren einerseits auf dem Konzept der mutants und andererseits auf dem parallelisierten Wiedemann-Algorithmus. Die Bedeutung dieser Verbesserungen wird anhand der Lösung von Systemen multivariater Polynomgleichungen, die ihren Ursprung in der Kryptographie haben, aufgezeigt. Deshalb sollten Designer neuer Kryptosysteme diesen neu vorgeschlagenen Algorithmen Beachtung schenken.

German
URN: urn:nbn:de:tuda-tuprints-26216
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 16 Jun 2011 11:00
Last Modified: 08 Jul 2020 23:55
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/2621
PPN: 267266448
Export:
Actions (login required)
View Item View Item