Information Technology Reference
In-Depth Information
tr
(
λ/a
)=0and
nl
r
(
D
a
f
λ
)
2otherwise.Notethat
g
λ/a
is such that
g
λ/a
(
x
+1) =
g
λ/a
(
x
). We have seen in Section 2.1 that this implies that
nl
r
(
g
λ/a
)
equals twice the
r
-th order nonlinearity of the restriction of
g
λ/a
to any linear hy-
perplane
H
excluding 1. Since the function
x
≥
nl
r
(
g
λ/a
)
−
→
x
2
+
x
is a linear isomorphism from
H
to the hyperplane
,weseethat
nl
r
(
g
λ/a
)equalstwicethe
r
-th order nonlinearity of the restriction of
f
λ/a
to this hyperplane. Applying then
Proposition 1, we deduce that
{
x
∈
F
2
n
/tr
(
x
)=0
}
2
n−
1
nl
r
(
D
a
f
λ
)
≥
2
nl
r
(
f
λ/a
)
−
−
2
tr
(
λ/a
)
(3)
(where
tr
(
λ/a
) is viewed here as an integer equal to 0 or 1). The first order
nonlinearity of the inverse function is lower bounded by 2
n−
1
2
n/
2
(it equals
this value if
n
is even). It has been more precisely proven in [41] that the charac-
ter sums
x∈F
2
n
(
−
1)
f
λ
(
x
)+
tr
(
ax
)
, called Kloosterman sums, can take any value
divisible by 4 in the range [
−
2
n/
2+1
+1
,
2
n/
2+1
+ 1]. This leads to:
−
Proposition 4.
[9] Let
F
inv
(
x
)=
x
2
n
−
2
,
x
∈
F
2
n
. Then we have:
(2
n
1
2
2
n−
1
nl
2
(
F
inv
)
≥
−
−
1)2
n/
2+2
+3
·
2
n
2
n−
1
2
3
n/
4
.
≈
−
In Table 1, for
n
ranging from 4 to 12 (for smaller values of
n
, the bound gives
negative numbers), we indicate the values given by this bound, compared with
the actual values computed by Fourquet et al. [29,35,28]. Note that Proposition 4
gives an approximation of the actual value which is proportionally better and
better when
n
increases. The difference between 2
n−
1
and our bound is in average
1.5 times the difference between 2
n−
1
and the actual value (for these values of
n
). In Table 2 we give, for
n
=13
,
14 and 15, the values given by our bound,
compared with upper bounds obtained by Fourquet et al. [28,29,35].
Table 1.
The values of the lower bound on
nl
2
(
F
inv
) given by Proposition 4, the actual
values and the ratio
n
4 5 6 7 8 9 10 11 12
bound 0 2 9 25 63 147 329 718 1534
values 2 6 14 36 82 182 392 842 1760
%
0 33 52 69 76 80
84
85
87
Table 2.
The values of the lower bound on
nl
2
(
F
inv
) given by Proposition 4, an
overestimation of the actual values and the ratio
13 14 15
the lower bound 3232 6740 13944
overestimation of the values 3696 7580 15506
%
n
87
89
90
