Information Technology Reference
In-Depth Information
-Since
nl
r
is ane invariant, this implies that, if there exists a nonzero vector
a
F
2
such that
f
(
x
+
a
)=
f
(
x
), then the best approximation of
f
by a function
of algebraic degree
r
is achieved by a function
g
such that
g
(
x
+
a
)=
g
(
x
)and
nl
r
(
f
)equalstwicethe
r
-th order nonlinearity of the restriction of
f
to any
linear hyperplane
H
excluding
a
.
- Note that the equality
nl
r
(
f
)=2
nl
r
(
f
0
)isalsotrueif
f
0
and
f
1
differ by a
function of algebraic degree at most
r
∈
−
1 since the function
x
n
(
f
0
+
f
1
)hasthen
algebraic degree at most
r
.
•
Conversely, the
r
-th order nonlinearity of the restriction of a function
f
to a
hyperplane is lower bounded by means of the
r
-th order nonlinearity of
f
:
Proposition 1.
[9] Let
f
be any
n
-variable Boolean function,
r
a positive in-
teger smaller than
n
and
H
an ane hyperplane of
F
2
. Then the
r
-th order
nonlinearity of the restriction
f
0
of
f
to
H
(viewed as an
(
n
−
1)
-variable func-
tion) satisfies:
2
n−
2
.
nl
r
(
f
0
)
≥
nl
r
(
f
)
−
2.2 On the Highest Possible
r
-th Order Nonlinearity (the Covering
Radius of the Reed-Muller Code of Order
r
)
The best known general upper bound on the first order nonlinearity of any
Boolean function is:
2
2
−
1
.
It can be directly deduced from the Parseval relation
a∈F
2
W
f
(
a
)=2
2
n
.It
is tight for
n
even and untight for
n
odd (some lower bounds on the covering
radius exist then, see e.g. [5]). This bound is obviously valid for (
n, m
)-functions
as well and it is then the best known bound when
m<n
.But,asprovedbyK.
Nyberg, it is tight (achieved with equality by the so-called bent functions) only
when
n
is even and
m
2
n−
1
nl
(
f
)
≤
−
≤
n/
2(seee.g.[6]).When
m
=
n
, we have the better
bound [16]:
2
n−
1
2
n−
1
nl
(
F
)
≤
−
,
2
which is achieved with equality (by the so-called almost bent functions) for every
odd
n
.For
m>n
further (better) bounds are given in [12] but no such bound
is tight. Improving upon all these bounds when they are not tight is a series of
dicult open problems.
The best known upper bound on the
r
-th order nonlinearity of any Boolean
function for
r
≥
2 is given in [14] and has asymptotic version:
√
15
2
(1 +
√
2)
r−
2
nl
r
(
f
)=2
n−
1
2
n/
2
+
O
(
n
r−
2
)
.
−
·
·
This bound is obviously also valid for vectorial functions. It would be nice to
improve it, for S-boxes, as the bound has been improved in the case
r
=1.We
leave this as an open problem.
