Information Technology Reference
In-Depth Information
and
σ
j
(
x
)isthe
j
th component of
σ
(
x
), so that
σ
(
x
)=(
σ
1
(
x
)
,...,σ
n
(
x
)). Now
write
w
(
x
) in 2-adic expansion, viz
w
(
x
)=
l
(
x
)+2
q
(
x
)with
n
l
(
x
)=
(
x
j
+
σ
j
(
x
))
(mod 2)
j
=1
n
q
(
x
)=
σ
j
(
x
)+
[(
x
j
x
k
+
σ
j
(
x
)
σ
k
(
x
)] +
x
j
σ
k
(
x
)(mod2
.
j
=1
1
≤j<k≤n
1
≤j,k≤n
Then we have
(
f
)(
u, v
)) = 2
−
2
−
1
(
ω
−n
i
wt(
v
)
1)
g
(
x
)+
q
(
x
)+
v·σ
(
x
)+
u·x
[1 + (
1)
l
(
x
)
]
N
(
−
−
x∈V
n
1
2
[
=
H
(
h
v
)(
u
)+
H
(
h
v
)(
u
)]
,
(5)
where
h
v
(
x
)=
g
(
x
)+
q
(
x
)+
v
·
σ
(
x
)and
u
is the complement of
u
. Similarly we
obtain
1
2
[
(
ω
−n
i
wt(
v
)
N
(
f
)(
u, v
)) =
H
(
h
v
)(
u
)
−H
(
h
v
)(
u
)]
.
(6)
By assumption,
|N
(
f
)(
u, v
)
|
= 1, and by Lemma 11, either the real part or the
imaginary part of
(
f
)(
u, v
) must be zero. First suppose that
n
is even. Then
ω
−n
is a 4th root of unity and either (5) or (6) must be zero. Hence
h
v
must
be bent for every
v
N
V
n
, which implies that for
n>
2 the degree of
h
v
can
be at most
n/
2[1].Nowlet
n
be odd. Then
ω
−n
is an 8th root of unity and
the absolute values of (5) and (6) must be equal. This can only happen if the
Hadamard spectrum of
h
v
contains only the values 0 and
∈
±
√
2 (such functions
are called almost-bent functions [2]). It is known [2, Thm. 1] that the degree of
such a function is at most (
n
+1)
/
2.
For either
n
≥
3 we conclude that the degree of
h
v
(
x
)isatmost
n/
2
for
every
v
∈
V
n
. This implies that the degree of
v
·
σ
(
x
) is bounded by
n/
2
for
every
v
∈
V
n
and
n
≥
3. Note that, since
σ
is a permutation,
σ
j
(
x
)
σ
k
(
x
)=1has
exactly 2
n−
2
3eachoftheterms
σ
j
(
x
)
σ
k
(
x
) cannot
have degree equal to
n
(see, e.g., [6, Ch. 13, Thm. 1]). Therefore, the degree of
q
is at most max
solutions in
V
n
,sofor
n
≥
. It follows that, if
n>
3, the degree of
q
and,
therefore, the degree of
g
is bounded by
n
{
n
−
1
,
n/
2
+1
}
−
1, which proves the theorem.
References
1. Rothaus, O.S.: On 'bent' functions. J. Comb. Theory (A) 20, 300-305 (1976)
2. Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suit-
able for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), 125-156
(1998)
3. Parker, M.G., Pott, A.: On Boolean functions which are bent and negabent. In:
Golomb, S.W., Gong, G., Helleseth, T., Song, H.-Y. (eds.) SSC 2007. LNCS,
vol. 4893, pp. 9-23. Springer, Heidelberg (2007)
