Information Technology Reference
In-Depth Information
∈
F
2
n
Lemma 1.
Let
H
:
F
2
n
→
F
2
n
be an arbitrary mapping. Then
γ
is a
linear structure of
Tr
H
(
x
2
+
γx
)+
βx
for any
β
∈
F
2
n
.
Next lemma describes another family of Boolean functions having a linear struc-
ture. Its proof is straightforward.
Lemma 2.
Let
F
:
∈
F
2
n
.Then
α
is a linear structure of
Tr
(
F
(
x
)+
F
(
x
+
α
)+
βx
)
for any
β ∈
F
2
n
.
F
2
n
→
F
2
n
and
α
In general, for a given Boolean function it is dicult to recognize whether it
admits a linear structure. Slightly extending results from [4], we characterize all
monomial Boolean functions assuming a linear structure. More precisely, for a
given nonzero
a
∈
F
2
n
, we describe all exponents
s
and nonzero
δ
∈
F
2
n
such
that
a
is a linear structure for the Boolean function
Tr
(
δx
s
).
Let 0
2
n
2. We denote by
C
s
the cyclotomic coset modulo 2
n
≤
s
≤
−
−
1
containing
s
:
s,
2
s,...,
2
n−
1
s
(mod 2
n
C
s
=
{
}
−
1)
.
x
s
Note that if
|
C
s
|
=
l
,then
{
|
x
∈
F
2
n
}⊆
F
2
l
and
F
2
l
is the smallest such
subfield.
The next lemma is an extension of Lemma 2 from [4].
2
n
∈
F
2
n
Lemma 3.
Let
0
≤
s
≤
−
2
,δ
be such that the Boolean function
Tr
(
δx
s
)
is a nonzero function. Then
a
∈
F
2
n
is a linear structure of the Boolean
function
Tr
(
δx
s
)
if and only if
(a)
s
=2
i
and
a
is arbitrary
(b)
s
=2
i
+2
j
(
i
=
j
)
and
(
δa
2
i
+2
j
)
2
n
−
i
+(
δa
2
i
+2
j
)
2
n
−
j
=0
.
∈
F
2
n
be a linear structure for
Tr
(
δx
s
). Then
Proof.
Let
a
Tr
(
δ
(
x
s
+(
x
+
a
)
s
))
≡
c
(2)
holds for all
x
∈
F
2
n
and a fixed
c
∈
F
2
. In [4] it is shown that in the case
|
=
n
the identity (2) can be satisfied only if the binary weight of
s
does not
exceed 2. On the other side it is easy to see that for an
s
of binary weight 1 the
corresponding Boolean function
Tr
(
δx
s
) is linear and thus any nonzero element
is a linear structure. If
s
=2
i
+2
j
,then
Tr
(
δ
(
x
2
i
+2
j
+(
x
+
a
)
2
i
+2
j
)) =
Tr
δa
2
i
+2
j
x
a
C
s
|
2
j
+
Tr
δa
2
i
+2
j
=
Tr
(
δa
2
i
+2
j
)
2
n
−
i
+(
δa
2
i
+2
j
)
2
n
−
j
x
a
2
i
+
x
a
+
Tr
δa
2
i
+2
j
,
