TU Darmstadt / ULB / TUprints

Improved Strategies for Solving Multivariate Polynomial Equation Systems over Finite Fields

Mohamed, Mohamed Saied Emam (2011)
Improved Strategies for Solving Multivariate Polynomial Equation Systems over Finite Fields.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
Mohamed-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: Improved Strategies for Solving Multivariate Polynomial Equation Systems over Finite Fields
Language: English
Referees: Buchmann, Prof. Johannes ; Ding, Prof. Jintai
Date: 14 June 2011
Place of Publication: Darmstadt
Publisher: TU Darmstadt
Date of oral examination: 6 June 2011
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage

Eine der wichtigen Fragestellungen in der Kryptographie ist das Problem, multivariate polynomiale Gleichungen über endlichen Körpern zu lösen. Die Komplexität dieses Problems ist das Maß für die Sicherheit vieler Public-Key-Kryptosysteme sowie vieler symmetrischer Kryptosysteme wie Block- und Stromchiffren. In den letzten Jahren wurde die algebraische Kryptanalyse als eine Methode des Angriffs auf Kryptosysteme vorgestellt. Diese Methode beruht auf der Lösung multivariater polynomialer Systeme. Daher ist die Entwicklung von Algorithmen zur Lösung solcher Systeme ein heißes Forschungsthema. In den letzten Jahren wurden verschiedene Algorithmen vorgeschlagen, multivariate polynomiale Systeme über endlichen Körpern zu lösen. Eine vielversprechende Methode hierbei basiert darauf, eine Lösung durch die Erweiterung des Systems durch Generierung zusätzlicher Gleichungen mit Hilfe von Techniken der linearen Algebra zu finden. Theoretische Abschätzungen der Komplexität haben ergeben, dass auf viele realistische Anwendungen algebraische Angriffe mit den derzeitigen Algorithmen nicht möglich sind. Der Grund hierfür ist die Tatsache, dass die Berechnungen mit diesen Algorithmen viel Zeit und Speicherressourcen erfordern. Eine große Herausforderung ist es daher, diese Algorithmen zu verbessern, um in der Lage zu sein, große multivariate polynomiale Systeme mit den in der Praxis begrenzt verf¨ugbaren Zeit- und Speicherressourcen zu l¨osen. In dieser Arbeit schlagen wir Strategien vor, um den Erweiterungsschritt dieser Algorithmen zu verbessern. Wir wenden diese Strategien aufgrund seiner einfachen Struktur auf den gut untersuchten XL-Algorithmmus an und zeigen, dass die Kombination dieser Strategien mit XL diesen zu einem im Vergleich mit State-of-the-art Algorithmen in hohem Maße wettbewerbsf¨ahigem Algorithmus macht. Im Jahre 2006 pr¨asentierte Jintai Ding das Konzept der mutants. Mutants sind Polynome von kleinerem als dem erwarteten Grad, die man w¨ahrend des Lineare-Algebra-Schrittes von XL erhält. Der in dieser Arbeit vorgestellte MutantXL-Algorithmus nutzt das Konzept der mutants um den Lösungsprozess des XL-Algorithmus zu verbessern. Der MXL2 -Algorithmus wird als eine verbesserte Version des MutantXL-Algorithmus eingeführt, indem eine partielle Erweiterungsstrategie entwickelt wird. Konkret ändern wir MutantXL in einer Weise, dass im Erweiterungsschritt die Menge der generierten Polynome bis zu einem bestimmten Grad D betrachtet wird, eine Teilmenge nach der anderen, ohne dass dazu die Menge der Polynome auf einmal gespeichert werden muss. Dies f¨uhrt zur Lösung von Systemen mit weniger erweiterten Polynomen als bei MutantXL. Der Hauptnachteil von MXL2 sowie XL und MutantXL ist es, dass nur Systeme mit einer einzigen Lösung gelöst werden können. Um Systeme mit einer endlichen Zahl von Lösungen zu lösen, präsentieren wir eine neue hinreichende Bedingung dafür, dass eine Menge von Polynomen eine Gröbnerbasis ist. Wir haben diese neue Bedingung als Abbruchkriterium des MXL2-Algorithmus benutzt. Diese Änderung wird gemeinsam mit weiteren Verbesserungen des Erweiterungsschrittes von MXL 2 in den MXL3-Algorithmus zur Berechnung von Gröbnerbasen eingeführt. Diese Arbeit stellt auch den MGB-Algorithmus vor, der eine flexible partielle Erweiterungsstrategie verwendet, um eine wesentliche Verbesserung gegenüber MXL3 zu bieten. Die am Ende der Arbeit vorgestellte vorläufige Studie schlägt eine neue Obergrenze für die Komplexität der Berechnung von Gröbnerbasen vor, die zu neuen Denkmodellen über die Komplexität von Gröbnerbasisberechnungen anregt. Die Ergebnisse dieser Arbeit zeigen, dass die vorgeschlagenen Strategien die Leistung des XL-Algorithmus dramatisch verbessern. Dar¨uber hinaus f¨urhren sie zu Algorithmen, die die MAGMA-Implementierung von F4 , einen der derzeit effizientesten Algorithmen, bezüglich Zeit und Speicherverbrauch in vielen Fällen übertrffen. Darüber hinaus wird eine angepasste Version des MutantXL-Algorithmus dazu verwendet, das MQQ Kryptosystem schneller und mit weniger Speicherverbrauch anzugreifen, als das mit F4 möglich ist.

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