Information Technology Reference
In-Depth Information
where
s
t
is the expanded state vector [
s
t
,...,s
t
+
n−
1
,s
t
s
t
+1
,...,s
t
+
n−
1
···
s
t
+
n−d
]. Thus, the equations in
F
are simply generated by
F
=
T
t
f
{
}
0
≤t≤m
for some
m
W
. In [19], the exact rank of the equation system
F
is deter-
mined. If
l
(
z
) denotes the degree of the minimal polynomial of the sequence
z
=
≤
{
z
t
}
t
=0
,
1
,...
, then we have that dim(
F
)=
m
where 0
≤
m
≤
ls
(
z
)
≤
W
.
There are basically two cases to consider:
-
A. if
m
=
l
(
z
)
W
, then the system can be solved using a linear subspace
attack or variations (see for instance [20]).
-
B. if
m<l
(
z
)
≤
W
, then the system of
m
linearly independent equations
may be solved using an XL-type algorithm.
≤
This just tells us that the systems coming from the filter generator satisfy the
two first restrictions in our analysis; that they are linearly independent and
have the same degree. But there is a possibility that the system may contain
nonlinear dependencies to begin with. For instance, the sequence
z
may satisfy
a nonlinear recursion
z
t
+
r
=
h
(
z
t
,z
t
+1
,...z
t
+
r−
1
)
,
0
≤
r
≤
m
, meaning that
f
t
+
r
=
h
(
f
t
,f
t
+1
,...,f
t
+
r−
1
)
,
0
m
. If such a relation exist, we do not
need to use a method like XL, since we may generate as many equations as
we need using the nonlinear recursion
h
. On the other hand, determining such
relations on practical systems seems to be a very hard problem.
But for a
D
m
and
D
e
where
D
=
D
m
+
D
e
, then if there are no nonlinear
relations between the
m
equations in
F
of degree
≤
r
≤
D
m
, our estimate of the
number of linearly independent equations will be exact since the system will
only contain relations that we construct ourselves. Thus if the smallest degree
of a nonlinear relation between the equations in
F
is
k
, then our analysis will be
exact when applying XL with
D
m
=
k
D
e
·
D
e
−
1, but not for
D
m
=
k
·
D
e
.
4 Preliminary Observations
Before we present an explanation of XLs behaviour, we give an intuitive presen-
tation of how to count the dependencies which occur in the application of an
algorithm such as XL.
We assume that the systems we study behave according to our assumptions
in Section 2 and use the notation introduced in Section 2. We will look at the
analysis of XL on quadratic systems presented in [11], and correct a mistake
made there. This will help to see how to systematically count the number of
linear dependencies created by XL.
Inthefollowing,weset
D
e
=2and
D
=
D
m
+
D
e
.In[11]theyuse
R
to count
the total number of equations, and set
S
to be the number of dependencies and
I
the number of linearly independent equations generated by XL, such that
I
=
R
−
S.
The authors do computer simulations on quadratic polynomial equations for
3
6 and identify some relations. For instance, for
D
= 4 they identify
two dependencies:
≤
D
≤
