Information Technology Reference
In-Depth Information
Corollary 1.
[9] Let
f
be any
n
-variable function and
r
a positive integer
smaller than
n
. Assume that, for some non-negative integers
K
and
k
, we have
nl
r−
1
(
D
a
f
)
2
n−
1
K
2
k
for every nonzero
a
F
2
,then
≥
−
∈
(2
n
1
2
2
n−
1
1)
K
2
k
+1
+2
n
nl
r
(
f
)
≥
−
−
√
K
2
(
n
+
k−
1)
/
2
.
2
n−
1
≈
−
As we shall see below, Corollary 1 can allow proving that a given infinite class
of functions has
r
-th order nonlinearity asymptotically equivalent to 2
n−
1
for
every
r
.
Applying two times Proposition 3, we obtain the bound
nl
r
(
f
)
≥
2
2
n
2
b∈F
2
1
2
2
n−
1
−
−
nl
r−
2
(
D
a
D
b
f
)
.
(2)
a∈F
2
These bounds are applied in [9] to some quadratic functions (whose low algebraic
degree makes them inappropriate for use in most cryptosystems) with good first
order nonlinearities to check that the approximation given by the bounds can
be good. Of most interest is what these bounds give in the case of the function
used as the S-box in the AES:
The multiplicative inverse function
is defined as
F
inv
(
x
)=
x
2
n
−
2
,where
n
is any positive integer and
x
ranges over the field
F
2
n
.Wedenote
f
λ
(
x
)=
tr
(
λx
2
n
−
2
), where
λ
is any element of
F
2
n
. All the Boolean functions
f
λ
,
λ
=0,
are anely equivalent to each others. We shall write
f
inv
for
f
1
.Butweshall
need however the notation
f
λ
in the calculations below. We have
f
λ
(
x
)=
tr
x
,
with the convention that
λ
0
= 0 (we shall always assume this kind of convention
in the sequel). Recall that the component functions of the Substitution boxes (S-
boxes) of the Advanced Encryption Standard (AES) - the current non-military
standard for block encryption [24] - are all of the form
f
λ
(with
n
=8).
The first order nonlinearity of
f
inv
is quite good, according to the extension
of the Weil bound first obtained by Carlitz and Uchiyama [15] and extended by
Shanbhag, Kumar and Helleseth [48] (see also the additional information on the
Walsh spectrum of the function by Lachaud and Wolfmann [41]). However, the
extension of the Weil bound is ecient only for
r
= 1. Indeed, already for
r
=2,
the degree of a quadratic function in trace representation form can be upper
bounded by 2
n/
2
+ 1 only and this gives a bound in 2
n
on the maximum mag-
nitude of the Walsh transform and therefore no information on the nonlinearity.
However, an effective bound can be obtained by using the recursive bound of
Proposition 3.
For every nonzero
a
F
2
n
,wehave(
D
a
f
λ
)(
ax
)=
tr
ax
+
ax
+
a
=
tr
x
2
+
x
λ/a
λ
∈
=
f
λ/a
(
x
2
+
x
)if
x
F
2
. We deduce, de-
noting
g
λ/a
(
x
)=
f
λ/a
(
x
2
+
x
)that,forevery
r
,wehave
nl
r
(
D
a
f
λ
)=
nl
r
(
g
λ/a
)if
∈
F
2
and (
D
a
f
λ
)(
ax
)=
tr
(
λ/a
)if
x
∈
