New Techniques for Polynomial System Solving

Since any encryption map may be viewed as a polynomial map between finite dimensional vector spaces over finite fields, the security of a cryptosystem can be examined by studying the difficulty of solving large systems of multivariate polynomial equations. Therefore, algebraic attacks lead to the task of solving polynomial systems over finite fields. In this thesis, we study several new algebraic techniques for polynomial system solving over finite fields, especially over the finite field with two elements. Instead of using traditional Gröbner basis techniques we focus on highly developed methods from several other areas like linear algebra, discrete optimization, numerical analysis and number theory. We study some techniques from combinatorial optimization to transform a polynomial system solving problem into a (sparse) linear algebra problem. We highlight two new kinds of hybrid techniques. The first kind combines the concept of transforming combinatorial infeasibility proofs to large systems of linear equations and the concept of mutants (finding special lower degree polynomials). The second kind uses the concept of mutants to optimize the Border Basis Algorithm. We study recent suggestions of transferring a system of polynomial equations over the finite field with two elements into a system of polynomial equalities and inequalities over the set of integers (respectively over the set of reals). In particular, we develop several techniques and strategies for converting the polynomial system of equations over the field with two elements to a polynomial system of equalities and inequalities over the reals (respectively over the set of integers). This enables us to make use of several algorithms in the field of discrete optimization and number theory. Furthermore, this also enables us to investigate the use of numerical analysis techniques such as the homotopy continuation methods and Newton's method. In each case several conversion techniques have been developed, optimized and implemented. Finally, the efficiency of the developed techniques and strategies is examined using standard cryptographic examples such as CTC and HFE. Our experimental results show that most of the techniques developed are highly competitive to state-of-the-art algebraic techniques.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Passau

Year

2012

Author dc:creator

• Ullah, Ehsan

Contributors dc:contributor

• Kreuzer, Martin

• polynomial system solving
• techniques
• linear algebra
• border bases
• mutant strategies

Statement dc:rights

• Standardbedingung laut Einverständniserklärung

Repository record source_url

https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/171

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-passau:171