Information Technology Reference
In-Depth Information
From the above analysis for three cases of
D
d
, we formerly define a nondegen-
erated case for
f
. For a given a positive integer
d
,wesaythat
f
is
nondegenerated
with respect to
d
if
.Inotherwords,
f
is nondegerated with respect
to
d
if and only if all the elements in
fS
d
are distinct and linearly indepen-
dent. We then obtain the condition which can remedy Assertion A, i.e., if
f
is
nondegenerated with respect to
d
, then it is true, as stated below.
|
D
d
|
=
|
S
d
|
Proposition 4.
For given
f
∈F
n
,andapairofpositiveintegers
(
d, e
)
,if
f
is nondegenerated with respect to
d
, then there exists a boolean function
g
∈F
n
with
deg
(
g
)
≤
d
such that
h
=
fg
=0
with
deg
(
h
)
≤
e
when
d
+
e
≥
n
.
Proof.
Since
D
d
is a linearly independent set, then
|
D
d
|
=
|
S
d
|
=
T
d
(recall
T
j
>
2
n
because
d
+
e
defined in (3)). If
T
=
D
d
∪
S
e
is independent, then
|
T
|
≥
n
.
2
n
2
,ithasmaximum2
n
linearly independent elements,
which is a contradiction. So, the elements in
T
are linearly dependent. Thus, the
assertion is true.
Since
T
is a subset of
F
From the proof of Proposition 4, we know that the condition
d
+
e
≥
n
guarantees
the existence of a multiplier
g
with
deg
(
g
)
≤
e
such that
h
=
fg
=0with
deg
(
h
)
≤
e
only if
f
is nondegenerated with respect to
d
.
5.2
Resistance against FAA
Recall that
AI
(
f
) denotes the algebraic immunity of
f
. Note that for any
g
such that
fg
=
h
=0,then
g
+
h
∈
Ann
(
f
) implies
deg
(
g
+
h
)
≥
AI
(
f
). If we
assume that
deg
(
g
)
≤
d<AI
(
f
), then
deg
(
h
)
≥
AI
(
f
). So
AI
(
f
)
≤
deg
(
h
)
≤
e
(otherwise, we swap
g
with
h
).
Definition 3.
For a given
f
∈F
n
,andapairofpositiveintegers
(
d, e
)
,
f
is
said to be
(
d, e
)
-resistance against FAA if and only if for all
g
with
deg
(
g
)
≤
d
and
h
=
fg
=0
with
deg
(
h
)
≥
e
. If the assertion is true for every
d
:1
≤
d<n
,
then
f
is said to be
e
-resistance against FAA
.
From Theorem 2, we have the following condition to determine whether a given
function is (
d, e
)-resistance against FAA.
Theorem 3.
Let
f
∈F
n
,
(
d, e
)
be an enable pair of
f
where
e>deg
(
f
)
,and
D
d
be a maximal linear independent set of
fS
d
.Then
f
is
(
d, e
)
-resistance against
FAA i f and on l y i f
|
D
d
|
=
|
S
d
|
and
D
d
∪
S
r
is linearly independent over
F
2
for
all
r
with
1
≤
r<e
and
D
d
∪
S
e
is linearly dependent over
F
2
.
Proof.
If
|
D
d
|
=
|
S
d
|
, i.e., all the elements in
fS
d
are linearly independent, then
h
=
fg
. From the second condition in Theorem 3, we know
that there are some
g
such that
h
=
fg
with
deg
(
h
)=
e
.Fotherestof
g
,
deg
(
h
)
>e
.Thus
f
is (
d, e
)-resistance against FAA.
Conversely, if there exists some
r
such that
D
d
∪
=0for
∀
g
∈
S
d
S
r
,1
≤
r<e
is linear
dependent over
F
2
, according to Theorem 2, there is some
g
∈
S
d
such that
h
=
fg
with
deg
(
h
)
≤
r<e
, which contradicts with
deg
(
h
)
>e
for any
g
.
