Information Technology Reference
In-Depth Information
This sucient condition is popularly recited in the literation for the study of
algebraic immunity of boolean functions (for example [17]). In this paper, using
an approach of the discrete Fourier transform (DFT) of boolean functions, we
investigate the characterizations of the existence of those multipliers. For a given
boolean function
f
in
n
variables and two positive integers
d
and
e
,weobserved
that the sucient condition
d
+
e
n
, shown in Assertion A cannot guarantee the
existence of a function
g
with
deg
(
g
)
≥
e
.
Pursuing this approach, we find a sucient and necessary condition for the
existence of such a multiplier
g
. From this sucient and necessary condition, we
obtain an algorithm to construct these multipliers. The other fascinating result
from this characterization is that there exist degenerated cases for which FAA
lost its advantages. We then introduce the concept of
resistance against
FAA.
This paper is organized as follows. In Section 2, we introduce the (discrete)
Fourier transform of boolean functions and sequences, their polynomial repre-
sentations, and bases of a 2
n
dimensional linear space in terms of
m
-sequences
together with their decimations and shifts. In Section 3, we first present a su-
cient condition for existence of multiplier
g
with
d
=
deg
(
g
) such that
h
=
fg
≤
d
such that
fg
=0with
deg
(
fg
)
≤
=0
with
deg
(
h
)
e
for a given function
f
and a pair of positive integers (
d, e
), then a
sucient and necessary condition, and thirdly, an algorithm for constructing such
multipliers. A characterization of those multipliers through the Reed-Muller code
is also provided. In Section 4, we discuss the degenerated cases and introduce
the concept of resistance against FAA. Section 5 is devoted to conclusions and
some discussions on trade-offs between polynomial representations and boolean
representations.
≤
2 Discrete Fourier Transform (DFT) of Boolean
Functions and Sequences and Their Polynomial Bases
We use the following notation throughout the paper.
2
-
F
q
=
GF
(
q
), a finite field with
q
elements, and
F
=
{
(
x
0
,x
1
,...,x
m−
1
)
|
x
i
∈
where
m
is a positive integer.
-A
boolean function
f
in
n
variables is a function from
F
2
}
2
to
F
F
2
. The algebraic
normal form of
f
is given by
f
(
x
0
,...,x
n−
1
)=
a
i
1
,...,i
t
x
i
1
...x
i
t
,a
i
1
,...,i
t
∈
F
2
where the sum runs through all the
t
-subset
{
i
1
,...,i
t
}⊂{
0
,
1
,...,n
−
1
}
.
The
degree
of the boolean function
f
is the largest
t
for which
a
i
1
,...,i
t
=0.
B
n
denotes the set of all boolean functions in
n
variables.
-If
S
=
{
e
0
,...,e
r−
1
}
F
2
,
is a linearly independent set of a linear space over
S
is a subspace generated by
S
.
then
-Let
S
⊂B
n
,then
S
0
is the set consisting of functions in
S
with zero constant
term.
-Let
S
and
T
be two subsets of
2
,then
S
+
T
=
F
{
s
+
t
|
s
∈
S, t
∈
T
}
and
ST
=
{
st
|
s
∈
S, t
∈
T
}
where the addition
s
+
t
and the multiplication
st
are
