Information Technology Reference
In-Depth Information
2 A Linear Structure of a Boolean Function
A Boolean function from
F
2
n
to
F
2
can be represented as
Tr
(
R
(
x
)) for some
(not unique) mapping
R
:
F
2
n
→
F
2
n
. A Boolean function
Tr
(
R
(
x
)) is said to
∈
F
2
n
have a linear structure
α
if
Tr
(
R
(
x
)) +
Tr
(
R
(
x
+
α
)) =
Tr
(
R
(
x
)+
R
(
x
+
α
))
is a constant function. We call a linear structure
c
-linear structure if
Tr
(
R
(
x
)+
R
(
x
+
α
))
≡
c,
∈
F
2
n
where
c
∈
F
2
,let
H
γ
(
c
) denote the ane hyperplane
defined by the equation
Tr
(
γx
)=
c
, i.e.,
∈
F
2
.Given
γ
and
c
H
γ
(
c
)=
{
x
∈
F
2
n
|
Tr
(
γx
)=
c
}
.
∈
F
2
n
is a
c
-linear structure for
Tr
(
R
(
x
)) if and only if the image set of
the mapping
R
(
x
)+
R
(
x
+
α
) is contained in the ane hyperplane
H
1
(
c
).
The Walsh transform of a Boolean function
Tr
(
R
(
x
)) is defined as follows
Then
α
1)
Tr
(
R
(
x
)+
λx
)
.
W
:
F
2
n
→
Z
,λ
→
(
−
x∈
F
2
n
Whether a Boolean function
Tr
(
R
(
x
)) has a linear structure can be recognized
from its Walsh transform.
∈
F
2
n
Proposition 1 ([2,8]).
Let
c
∈
F
2
and
R
:
F
2
n
→
F
2
n
.Anelement
α
is
a
(
c
+1)
-linear structure for
Tr
(
R
(
x
))
if and only if
(
λ
)=
x∈
F
2
n
1)
Tr
(
R
(
x
)+
λx
)
=0
W
(
−
for all
λ
∈
H
α
(
c
)
.
In [5] all Boolean functions assuming a linear structure are characterized as
follows.
Theorem 1 ([5]).
Let
R
:
F
2
n
→
F
2
n
. Then the Boolean function
Tr
(
R
(
x
))
has a linear structure if and only if there is a non-bijective linear mapping
L
:
F
2
n
→
F
2
n
such that
Tr
(
R
(
x
)) =
Tr
H
L
(
x
)+
βx
+
c,
◦
where
H
:
F
2
n
→
F
2
n
,β
∈
F
2
n
and
c
∈
F
2
.
Clearly, any element from the kernel of
L
is a linear structure of
Tr
(
R
(
x
))
considered in Theorem 1. Moreover, those are the only ones if the mapping
Tr
(
H
(
x
)) has no linear structure belonging to the image of
L
. We record this
observation in the following lemma to refer it later.
