Information Technology Reference
In-Depth Information
-
F
λ
≤D
:Fiscontainedin
U
D
which is a subset of all polynomials
of degree less or equal to
D
.
-
The total number of polynomials in
U
D
after an execution of XL is
⊆
U
D
⊆
|
U
D
|
=
i
=0
i
, but these are not necessarily linearly independent.
The XL algorithm can now be described as follows (adapted from original paper):
·
D
m
m
Algorithm (The XL algorithm).
For a positive integer
D
m
and a set of
polynomial equations
F
=
{
f
1
,...,f
m
}
, execute the following steps:
1.
Multiply
: Generate all the products
m
·
f
i
∈
U
D
,
1
≤
deg(
m
)
≤
D
m
,f
i
∈
F
2.
Linearize
: Consider each monomial
D
as a new variable
and perform Gaussian elimination on the equations obtained in Step 1.
3.
Solve or Repeat
: If the system is not solved, increase
D
m
andredostep1
and 2.
m
with
deg
(
m
)
≤
Remark 1.
Setting
D
e
= 2 gives the algorithm from [10].
The idea behind the algorithm is that new linearly independent equations are in
fact generated. But this comes at the expense of increasing the total degree
D
of the system
U
D
. In [12] it is shown that XL is basically the construction of the
Macaulay matrix. Lazard (see [17] and [18]) describes the link between linear
algebra and computing Grobner bases and proves that Gaussian elimination on
the Macaulay matrix for
D
large enough returns a Grobner basis. Thus the
problem presented above can be reformulated as:
Problem 1.
For which
D
will the XL algorithm, after a row reduction of
U
D
with
respect to a monomial ordering, return a matrix with full rank?
It should be noted that the fastest Grobner basis algorithm, Faugeres
F
5
algo-
rithm, is based on the same type of computation as XL. However,
F
5
differs
from XL in that it avoids computing unnecessary linear dependencies. But our
result applies also to the case of
F
5
, as both algorithms reach the same degree
D
before a linear basis can be computed.
2.2 Restrictions on F
Exact analysis becomes very hard, if not impossible, if we assume nothing about
the polynomials in
F
. The best approach is to define a suciently general re-
striction on the system
F
in which the algorithm can be analyzed in fair terms.
In this section we define some restrictions on
F
, which is almost always fulfilled
for systems coming from cryptography.
First, we put the following restrictions on
F
:
-
Total degree: deg(
f
i
)=
D
e
,
∀
f
i
∈
F
.
-
All [
f
i
] are linearly independent.
We will also restrict
F
by defining the types of relations which occur between
the polynomials.