Project Topics
Get Complete Project Material File(s) Now! »
Algebraic techniques for solving the MinRank problem
Minors modeling. The direct and most straightforward way to represent the MinRank as a system of polynomial equations is to consider the set of all minors of size r+1 of the matrixM0 − Pn i=1 λiMi. Indeed, those minors simultaneously vanish exactly at the solutions of the MinRank problem. However, the drawback of this modeling is the size of the polynomial system. For instance, if n = 9,
r = 9, p = q = 12, there are 220 minors of size 10, and each one is a dense polynomial of degree 10 in 9 variables: each one is the sum of 19 10 = 92378 monomials.
Kipnis-Shamir modeling. The Kipnis-Shamir modeling was introduced in [KS99] and yields a way to represent MinRank problems as systems of bilinear equations. Roughly speaking, the idea to represent the locus of rank defect of the matrix M is to introduce fresh variables representing the kernel of the matrix. This is in the same spirit as Lagrange multipliers in optimization. It is done by looking for a triangular basis of the right kernel of the matrix M0 − Pn i=1 λiMi. Indeed, this matrix has rank at most r if and only if its right kernel has dimension at least q − r. We assume moreover that this right kernel is in systematic form, i.e. that the projection on the last coordinates KerR(M0 − Pn i=1 λiMi) → Kq−r (y1, . . . , yq) 7→ (yr+1, . . . , yq).
Hidden Field Equations (HFE)
Hidden Field Equations (HFE for short) is an asymmetric encryption scheme proposed in [Pat96]. Its security against message recovery attacks relies on the difficulty of solving boolean systems. However, in [FJ03], the authors show that these boolean systems are actually structured and that this structure can be exploited during Gr¨obner basis computations. We give here a short and simplified description of HFE. We refer the reader to [KS99] for more details.
The main idea of HFE is that the secret key is a univariate polynomial over an extension field GFqn. This polynomial has a special shape: P(x) = X 0≤i,j≤r ai,jxqi+qj .
Algebraic Tools for Real Solving
Critical Point Method. The problem of polynomial optimization can be algebraically represented as follows: a local extrema x of P restricted to the real trace of V = Z(f1, . . . , fp) is also a critical point of the restriction of P to V . Therefore, the evaluation at any local extrema x of the Jacobian matrix is rank defective. Therefore, xmin is a real zero of the system of polynomials {f1, . . . , fp} ∪ MaxMinors(jac(P, f1, . . . , fp)).
Under mild genericity assumptions, this system is 0-dimensional (see Chapter 5), so Gr¨obner basis techniques can be used to obtain a rational parametrization of the real local extrema of the restriction of P to V .
Under these genericity assumptions, the system {f1, . . . , fp} ∪ MaxMinors(jac(P, f1, . . . , fp)) is the union of a regular sequence (f1, . . . , fp) and of a determinantal system MaxMinors(jac(P, f1, . . . , fp)). This kind of systems is studied in Chapter 5. Notice that it is also possible to express the rank condition of the Jacobian matrix by using Lagrange multipliers, i.e. a set of fresh variables modeling a vector in the kernel.
More generally, the critical point method can be used to study any semi-algebraic set V : the critical points of the projection on the first coordinate πi : V ∩ Rn −→ Ri.
Structure of multi-homogeneous ideals
In this section, we recall several known results on multi-homogeneous ideals. For simplicity of notations, most results are only stated for bilinear systems but they can be easily extended to multihomogeneous systems.
When f1, . . . , fm is a bi-homogeneous system in K[x0, . . . , xnx, y0, . . . , yny ] (with degree at least 1 with respect to each block of variables), there is a set of trivial solutions that we need to take into account: the varieties Z(x0, . . . , xnx) and Z(y0, . . . , yny ) are necessarily subsets of Z(f1, . . . , fm). The corresponding ideals hx0, . . . , xnxi and hy0, . . . , yny i are called the irrelevant ideals. Contrary to the classical homogeneous case, these irrelevant ideals are not maximal, and this fact has several consequences: for instance, as soon as m ≥ nx + 1, regular bi-homogeneous sequences of size m do not exist.
In the section, we recall tools to transpose some results on homogeneous ideals in this context. Roughly speaking, the objective is to show that there exists a generic property of bi-homogeneous systems which is similar to regularity for homogeneous systems. We use the following notations: Notations 3.5. • BLK(nx, ny) the K-vector space of bilinear forms in K[X, Y ] = K[x0, . . . , xnx, y0, . . . , yny ];
• X (resp. Y ) is the ideal hx0, . . . , xnxi (resp. hy0, . . . , yny i).
• An ideal is called bihomogeneous if it admits a set of bihomogeneous generators.
• If (f1, . . . , fm) ∈ BLK(nx, ny)m is a family of bilinear forms, Ii denotes the ideal hf1, . . . , fii and Ji denotes the saturated ideal Ii : (X ∩ Y )∞.
Table of contents :
Introduction
I Preliminaries
1 Gr¨obner bases
1.1 Polynomial Rings and Ideals
1.1.1 Definitions
1.1.2 Modules, algebras and free resolutions
1.1.3 Primary decomposition and associated primes
1.2 Monomial orderings and Gr¨obner bases
1.2.1 Definitions
1.2.2 Gradings on polynomial rings
1.2.3 Regular and Semi-regular Sequence
1.2.4 Boolean semi-regular systems.
1.3 Polynomial system solving
1.3.1 Gr¨obner basis Algorithms
1.3.2 Matrix F5 Algorithm
1.3.3 FGLM Algorithm
1.4 Degree bounds
1.4.1 Definitions
1.4.2 Degree of regularity
1.4.3 Relations between notions of regularity
1.5 Complexity
1.5.1 Complexity model
1.5.2 Complexity of Gr¨obner basis algorithms
1.5.3 Complexity of solving affine systems
1.5.4 Complexity and degree of the ideal
2 Algebraic Systems in Applications
2.1 MinRank
2.1.1 Description of the MinRank problem
2.1.2 Algebraic techniques for solving the MinRank problem
2.2 Cryptology and Information Theory
2.2.1 Courtois Authentication Scheme
2.2.2 Rank metric codes
2.2.3 Hidden Field Equations (HFE)
2.2.4 McEliece PKC.
2.2.5 QUAD
2.2.6 The Algebraic Surface Cryptosystem
2.3 Real Solving and Optimization
2.3.1 Problem statements
2.3.2 Algebraic Tools for Real Solving
3 Determinantal and multi-homogeneous systems
3.1 Determinantal systems
3.2 Structure of multi-homogeneous ideals
3.3 Affine bilinear systems
II Contributions
4 Determinantal Systems
4.1 Introduction
4.2 Notations and preliminaries
4.3 Transferring determinantal properties
4.4 The case n ≥ (p − r)(q − r)
4.5 The over-determined case
4.6 Complexity analysis
4.6.1 Positive dimension
4.6.2 The 0-dimensional affine case
4.7 Case studies
4.7.1 D grows, p, q, r are fixed
4.7.2 p grows, q, r,D are fixed
4.7.3 The case r = q − 1
4.7.4 Experimental results
5 Critical Point Systems
5.1 Introduction
5.2 Preliminaries
5.3 The homogeneous case
5.3.1 Auxiliary results
5.3.2 Proof of Proposition 5.7
5.4 The affine case
5.5 Complexity
5.6 Experimental Results
5.7 Mixed systems
5.7.1 Eagon-Northcott complex
5.7.2 Hilbert series, degree of regularity
5.7.3 Complexity
6 Multi-Homogeneous Systems
6.1 Introduction
6.2 Computing Gr¨obner bases of bilinear systems
6.2.1 Overview
6.2.2 Jacobian matrices of bilinear systems and syzygies
6.2.3 Maximal minors of linear matrices
6.2.4 An extension of the F5 criterion for bilinear systems
6.3 F5 without reduction to zero for generic bilinear systems
6.3.1 Main results
6.3.2 Kernel of matrices whose entries are linear forms
6.3.3 Structure of generic bilinear systems
6.4 Hilbert bi-series of bilinear systems
6.5 Towards complexity results
6.5.1 A multihomogeneous F5 Algorithm
6.5.2 Complexity estimates
6.5.3 Number of reductions to zero
6.5.4 Structure of generic affine bilinear systems
6.5.5 Affine bilinear systems – maximal degree reached
6.6 Bi-homogeneous systems of bi-degree (D, 1)
7 Boolean Systems
7.1 Introduction
7.2 Algorithm
7.2.1 Macaulay matrix
7.2.2 Witness degree
7.2.3 Algorithm
7.2.4 Testing Consistency of Sparse Linear Systems
7.3 Complexity Analysis
7.3.1 Sizes of Macaulay Matrices
7.3.2 Bound on the Witness Degree of Inconsistent Systems
7.3.3 Complexity
7.4 Numerical Experiments on Random Systems
7.4.1 γ-strong semi-regularity
7.4.2 Numerical estimates of the complexity
7.5 Extensions and Applications
7.5.1 Adding Redundancy to Avoid Rank Defects
7.5.2 Improving the quality of the filtering for small values of n
7.5.3 Cases with Low Degree of Regularity
8 Application to Cryptology
8.1 Cryptanalysis of the Algebraic Surface Cryptosystem
8.1.1 Introduction
8.1.2 Description of the cryptosystem
8.1.3 Description of the attack
8.1.4 Level 1 Attack: decomposition of ideals.
8.1.5 Level 2 Attack: computing in the field of fractions GFp(t)
8.1.6 Level 3 Attack: computing in finite fields GFpm
8.1.7 Complexity analysis
8.1.8 Experimental results
8.1.9 Conclusion
8.1.10 Toy example
8.1.11 MAGMA code for the Level 1 Attack
8.2 Cryptanalysis of MinRank
8.2.1 Computing the minors
8.2.2 The well-defined case
8.2.3 Solving the challenge C of the Courtois authentication scheme
8.3 Analysis of QUAD
