Information Technology Reference
In-Depth Information
Table 3.
The values of the lower bound on
nl
2
(
F
inv
) given by Proposition 3 and the
FFT algorithm
n 4 5 6 7 8 9 10 11 12
Prop. 3 2 5 12 30 69 156 340 731 1551
Table 4.
The values of the lower bounds on
nl
3
(
F
inv
) given by Proposition 5
n
7 8 9 10 11 12 13
bound of Proposition 5 5 20 58 149 358 827 1859
Proposition 3 gives nicer results than those deduced from Proposition 4 and
listed in Table 1, when using the fast FFT algorithm to compute (exactly, instead
of having a lower bound) the nonlinearities of the derivatives of the inverse
function: see Table 3.
A bound for the whole nonlinearity profile of the inverse function.
Thanks to Relations (2) and (3), we have:
Proposition 5.
[9] Let
F
inv
(
x
)=
x
2
n
−
2
. Then we have:
nl
3
(
F
inv
)
2
n−
1
≥
−
(2
n
1)
√
2
3
n/
2+3
+3
1
2
2
n−
1
2
7
n/
8
−
1
/
4
.
−
·
2
n
+1
−
2
n/
2+3
+16
≈
−
In Table 4, for
n
ranging from 7 to 13, we indicate the values given by this bound
(for
n<
7 it gives nothing better than 0).
The process leading to Proposition 5 can be iteratively applied, giving a lower
bound on the
r
-th order nonlinearity of the inverse function for
r
≥
4. The
expression of this lower bound is:
2
n−
1
nl
r
(
F
inv
)
≥
−
l
r
,
where, according to Relation (3) and to Corollary 1, the sequence
l
r
is defined by
l
1
=2
n/
2
and
l
r
=
(2
n
1)(
l
r−
1
+1)+2
n−
2
. The expression of
l
r
is more and
more complex when
r
increases. Its value is approximately equal to 2
k
r
,where
k
1
=
n/
2and
k
r
=
−
n
+
k
r−
1
2
2
−r
)
n
. Hence,
nl
r
(
F
inv
)is
, and therefore
k
r
=(1
−
2
(1
−
2
−r
)
n
and asymptotically equivalent
approximately lower bounded by 2
n−
1
−
to 2
n−
1
,whateveris
r
.
3 Generalizations of the Higher Order Nonlinearity for
S-Boxes
There are two natural extensions of the notion of higher order nonlinearity of
S-boxes:
