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.
Search WWH ::




Custom Search