Information Technology Reference
In-Depth Information
Proof.
Rearranging the first expression, using the proposition and substituting
for
D
and
k
we get
D
D
e
+1
1)
i
m
+
i
D
m
−
(
i−
1)
D
e
n
j
.
−
1
I
=
T
−
(
−
i
i
=0
j
=0
The
T
can be expressed as
T
=
D
e
+
D
m
j
=0
j
,whichisthetermfor
i
=0inthe
sum. Canceling these terms we are left with
(
−
1)
i
m
+
i
D
m
−
(
i−
1)
D
e
n
j
.
D
D
e
+1
−
1
I
=
−
i
i
=1
j
=0
We can let the sum start at
i
= 0 by subtracting 1 from the upper limit for
i
and increasing each
i
in the rest of the expression by 1. Compensating for the
minus sign in front of the sum we get
D
D
e
1)
i
m
+
i
i
+1
D
m
−iD
e
n
j
.
I
=
(
−
i
=0
j
=0
The corollary shows that Theorems 3 and 2 are basically the same result. With
the proof of Theorem 2 we have also proved Theorem 3 with equality when as-
suming that only trivial linear dependencies occur. Many computer experiments
on random systems (with no restrictions on the dependencies), counting the
number of linearly independent equations have been done, both by us and the
authors of Theorem 3. In these experiments it has never occurred that Theorem 3
fails, so we believe that the result is correct and end this section with the fol-
lowing conjecture.
Conjecture 1.
Let
I
be the number of linearly independent polynomials in
n
variables generated by step 1 of the XL algorithm, where all
m
initial equations
have degree
D
e
and we multiply with all monomials up to degree
D
m
.Then
D
D
e
1)
i
m
+
i
i
+1
D
m
−ik
n
j
.
I
≤
(
−
i
=0
j
=0
7 Conclusions
The work in this paper comes from the field of cryptography, in particular al-
gebraic attacks on symmetric key ciphers. The complexity of such attacks has
been hard to estimate, but this paper shows the XL-algorithm generates a lot
of linearly dependent equations and is not as ecient as initially hoped.
Using the formula in Theorem 2, we can predict the smallest
D
for which the
XL algorithm will work over
F
2
. The formula is easier to use than that of Yang
and Chen, since no multiplication of polynomials or series is involved, but only
simple arithmetic.
