Information Technology Reference
In-Depth Information
attempt, by Iwata-Kurosawa [34], to construct functions with lower bounded
r
-
th order nonlinearity. But the obtained value, 2
n−r−
3
(
r
+ 5), of the lower bound
was small.
In the present paper, we give a survey of the state of the art in the domain:
some simple observations, the lower bounds on the higher order nonlinearity of a
Boolean function with given algebraic immunity, a recent recursive lower bound
(a lower bound on the
r
-th order nonlinearity of a given function
f
, knowing a
lower bound on the (
r
1)-th order nonlinearity of the derivatives of
f
), and
the deduced lower bounds on the whole nonlinearity profile of the multiplicative
inverse function. We also give new results. We show that, when considering an
S-box instead of a Boolean function, we can prove better bounds involving the
algebraic immunity, on the higher order nonlinearity. We begin the study of a
more general notion of higher order nonlinearity of S-boxes, which poses many
interesting problems.
−
2 Higher Order Nonlinearity of Boolean Functions and
S-Boxes
2.1 Some Simple Facts
•
Adding to a function
f
a function of algebraic degree at most
r
clearly does
not change the
r
-th order nonlinearity of
f
.
•
Since
RM
(
r, n
) is invariant under any ane automorphism, composing a Boo-
lean function by an ane automorphism does not change its
r
-th order nonlin-
earity (i.e. the characteristic
nl
r
is ane invariant). And composing an S-box by
ane automorphisms on the left and on the right does not change its
r
-th order
nonlinearity.
•
The minimum distance of
RM
(
r, n
) being equal to 2
n−r
for every
r
≤
n
,we
have
nl
r
(
f
)
n
.
Moreover, any minimum weight function
f
of algebraic degree
r
+ 1 (that is, the
indicator - i.e. the characteristic function - of any (
n
≥
2
n−r−
1
for every function
f
of algebraic degree exactly
r
+1
≤
−
r
−
1)-dimensional flat,
see [43]), has
r
-th order nonlinearity equal to 2
n−r−
1
since a closest function of
algebraic degree at most
r
to
f
is clearly the null function.
•
As observed by Iwata and Kurosawa [34] (for instance), if
f
0
is the restriction
of
f
to the linear hyperplane
H
of equation
x
n
=0and
f
1
the restriction of
f
to
the ane hyperplane
H
of equation
x
n
= 1 (these two functions will be viewed
as (
n
nl
r
(
f
0
)+
nl
r
(
f
1
) since, for
every function
g
of algebraic degree at most
r
, the restrictions of
g
to
H
and
H
having both algebraic degree at most
r
,wehave
d
H
(
f, g
)
−
1)-variable functions), then we have
nl
r
(
f
)
≥
nl
r
(
f
0
)+
nl
r
(
f
1
)
where
d
H
denotes the Hamming distance (obviously, this inequality is more
generally valid if
f
0
is the restriction of
f
to any linear hyperplane
H
and
f
1
its
restriction to the complement of
H
).
-Moreover,if
f
0
=
f
1
, then there is equality since if
g
is the best approximation
of algebraic degree at most
r
of
f
0
=
f
1
,then
g
now viewed as an
n
-variable
function lies at distance 2
nl
r
(
f
0
)from
f
.
≥
