Information Technology Reference
In-Depth Information
5.1
Degenerated Cases
Case 1.
fS
d
=
: Weak Functions.
From Corollary 3-(b), for given
f
{
f,
0
}
∈F
n
and
d
, a positive integer, there is an
extremely degenerated case, i.e.,
fg
=0
,
for all
g
∈
<S
d
>
0
(27)
where
S
d
0
is defined as the subspace of
S
d
with zero constant term, i.e.,
g
(0) =
2
n
matrix for which the row vectors are given by
P
k
,w
(
k
)
0. Let
M
be a
T
d
×
d
(see (19) for the definition of
P
k
). We write
f
=(
f
(0)
,x
0
,...,x
2
n
−
2
)where
x
i
=
f
(
α
i
). Then
f
satisfies the condition (27) if and only if
≤
Mf
=0
.
This is equivalent to that
f
is in the null space of
M
, denoted as
V
.Thus,any
function in
V
satisfies (27). By the linear algebra, the dimension of
V
is given
by 2
n
−|
S
d
|
. On the other hand, the set consisting of all functions with degree
≤
d
is given by
S
d
=
S
d
0
∪
S
d
1
,where
S
d
1
is the complement of
S
d
0
.
Therefore, for any
g
1
∈
S
d
0
,wehave
f
(
g
1
+1)=
fg
1
+
f
=
f
since
fg
1
=0.
Thus we have
g
=
g
1
+1 with
deg
(
g
)=
deg
(
g
1
)
d
and
h
=
f
with degree
deg
(
h
)=
deg
(
f
). However, those functions have the lowest algebraic immunity,
which is 1. Note that in this case we have
≤
S
d
0
=
Ann
(
f
), the set consisting
of all functions
g
such that
fg
= 0 (see (5) in Section 1). Then any enable pair
is given by (
i, deg
(
f
)) where 1
d
. Those functions are very poor in terms
of the resistance against both the algebraic attack and FAA. We summarize the
above discussion in the following proposition.
≤
i
≤
2
n
Proposition 3.
Let
V
be the nul l space of
M
in
F
2
.
1. For each
f
<S
d
>
0
.
2. All enable pairs of
f
are in the form of
(
i, deg
(
f
))
where
1
∈
V
,
fg
=0
∀
g
∈
d
.
3. The algebraic immunity of
f
is equal to 1, and
Ann
(
f
)=
<S
d
>
0
.
≤
i
≤
Case 2.
|
where
D
d
is the maximal independent subset of
fS
d
.From
Theorem 2 and Corollary 3, if
D
d
|
<
|
S
d
|
|
D
d
|
<
|
S
d
|
, then we also have some enable pairs
in the form of (
i, deg
(
f
)) with 1
≤
i
≤
d
for those
g
∈
S
d
such that
g
=
g
1
+1
where
fg
1
=0
,g
1
∈
S
d
0
.If
g
∈
S
d
0
such that
h
=
fg
=0,therearetwo
cases as follows.
(a) If
D
d
∪
S
e
are linearly dependent, then
deg
(
h
)
≤
e
.
(b) If
D
d
∪
S
e
are linearly independent, then
deg
(
h
)
>e
.
Furthermore, any enable pair of
f
belongs to one of the following patterns:
(
i, deg
(
f
)) where 1
≤
i
≤
d
or (
i, j
)where1
≤
i
≤
d
;1
≤
j<n.
Case 3.
|
D
d
|
=
|
S
d
|
. In this case, for each
g
∈
S
d
,
fg
=0.Italsohastwo
phenomena as stated in (a) and (b) in Case 2.
