Information Technology Reference
In-Depth Information
bent-negabent function in 2
n
variables is also equal to
n
. For example, the cubic
function
f
:
V
6
→
F
2
f
(
x
1
,x
2
,x
3
,y
1
,y
2
,y
3
)=
y
1
(
x
1
x
2
+
x
2
x
3
+
x
1
+
x
2
)+
y
2
(
x
1
x
2
+
x
2
x
3
+
x
3
)+
y
3
(
x
1
+
x
3
)
is bent-negabent. Note that
f
belongs to the Maiorana-McFarland class. In this
section we prove that the degree of a Maiorana-McFarland-type bent-negabent
function in 2
n
variables is at most
n
−
1for
n>
3.
Theorem 10.
Let
σ
be a permutation on
V
n
and let
g
:
V
n
→
F
2
be an arbitrary
Boolean function. Suppose that the function
f
:
V
n
⊕ V
n
→
F
2
given by
f
(
x, y
)=
σ
(
x
)
·
y
+
g
(
x
)
is negabent. Then, if
n>
3
, the degree of
f
is at most
n
−
1
.
The proof of the theorem requires a lemma.
Lemma 11.
The nega-Hadamard transform of a negabent function on
V
n
con-
tainsonlyvaluesoftheform
ω
n
i
k
,where
ω
=(1+
i
)
/
√
2
and
k
∈
Z
4
.
Proof.
Let 2
−
2
S
denote an arbitrary value of the nega-Hadamard transform of
a negabent function on
V
n
.Then
2
=2
n
must be a sum of two squares (one of them may be zero). From Jacobi's two-
square theorem we know that 2
n
has a unique representation as a sum of two
squares, namely 2
n
=(2
n/
2
)
2
+0
2
if
n
is even, and 2
n
=(2
(
n−
1)
/
2
)
2
+(2
(
n−
1)
/
2
)
2
if
n
is odd. Hence, if
n
is even, either
(
S
)or
(
S
)mustbeintegersand
|
S
|
(
S
)or
(
S
) must be zero. If
n
is odd,
we must have
|
(
S
)
|
=
|
(
S
)
|
, which proves the lemma.
Proof (of Theorem 10).
Using Lemma 1, we obtain
(
f
)(
u, v
)=2
−n
1)
σ
(
x
)
·y
+
g
(
x
)+
u·x
+
v·y
i
wt(
x
)+wt(
y
)
N
−
(
x,y∈V
n
=2
−n
1)
g
(
x
)+
u·x
i
wt(
x
)
1)
(
σ
(
x
)+
v
)
·y
i
wt(
y
)
(
−
(
−
x∈V
n
y∈V
n
=2
−
2
ω
n
1)
g
(
x
)+
u·x
i
wt(
x
)
−
wt(
σ
(
x
)+
v
)
(
−
x∈V
n
=2
−
2
ω
n
i
−
wt(
v
)
1)
g
(
x
)+
u·x
+
v·σ
(
x
)
i
wt(
x
)
−
wt(
σ
(
x
))
(
−
x∈V
n
2
ω
n
i
−
wt(
v
)
=2
−
1)
g
(
x
)+
u·x
+
v·σ
(
x
)
i
w
(
x
)
,
(
−
x
∈
V
n
where
n
w
(
x
)=
(
x
j
+3
σ
j
(
x
))
(mod 4)
j
=1