Information Technology Reference
In-Depth Information
minimum Hamming distance between
f
and all functions of algebraic degrees
at most
r
(in the case of
r
= 1, we shall simply write
nl
(
f
)). In other words,
nl
r
(
f
) equals the distance from
f
to the Reed-Muller code
RM
(
r, n
)oflength
2
n
and of order
r
, that is, the number of bits to change in the truth table of
f
to
get a Boolean function of algebraic degree at most
r
). This parameter is called
the
r
-th order nonlinearity
of
f
(simply the nonlinearity in the case
r
=1).The
maximum
r
-th order nonlinearity of all Boolean functions in
n
variables equals
by definition the covering radius of
RM
(
r, n
)[19].The
nonlinearity profile
of a
function
f
is the sequence of those values
nl
r
(
f
)for
r
ranging from 1 to
n
1.
The same notion can be defined for S-boxes in stream or block ciphers as
well, that is, for vectorial Boolean functions
F
:
F
2
→
−
F
2
(also called (
n, m
)-
functions). Such functions are used in stream ciphers in the place of Boolean
functions to speed up the enciphering and deciphering processes (since they
output
m
bits instead of one at each clock cycle). They are used as well (and
more systematically) in block ciphers to bring
confusion
[49] into the system. The
algebraic degree of an S-box is the maximum algebraic degree of its coordinate
functions. We shall denote by
nl
r
(
F
) the minimum
r
-th order nonlinearity of all
the
component functions
F
,where
ranges over the set of all the nonzero linear
forms over
F
2
(hence, the component functions are those linear combinations
of coordinate functions whose coecients are not all-zero). Equivalently,
nl
r
(
F
)
is the minimum
r
-th order nonlinearity of all the functions
v
◦
F
2
·
F
,
v
∈
\{
0
}
,
” denotes the usual inner product in
F
2
(or any other inner product). If
F
2
is endowed with the structure of the field
F
2
m
,then
nl
r
(
F
) is the minimum
r
-th order nonlinearity of all the functions
tr
(
vF
(
x
)),
v
where “
·
F
2
m
. The algebraic
degree of an S-box is also the maximum degree of its component functions.
The cryptographic relevance of the higher order nonlinearity has been illus-
trated by several papers [20,33,34,40,44,47,50]. Computing the
r
-th order non-
linearity of a given Boolean function with algebraic degree strictly greater than
r
is a hard task for
r>
1. In the case of the first order, much is known in theory
and also algorithmically since the nonlinearity is related to the Walsh transform,
which can be computed by the algorithm of the Fast Fourier Transform (FFT).
Recall that the Walsh transform of
f
is the Fourier transform of the “sign”
function (
∈
as
W
f
(
a
)=
x∈F
2
(
1)
f
, defined at any vector
a
F
2
1)
f
(
x
)+
x·a
−
∈
−
a
is an inner product in
F
2
- when the vector space
F
2
is identified to
the field
F
2
n
,wecantake
x
(where
x
·
a
=
tr
(
xa
)). The relation between the nonlinearity
and the Walsh transform is well-known:
nl
(
f
)=2
n−
1
·
1
.But
for
r>
1, very little is known. Even the second order nonlinearity is known only
for a few peculiar functions and for functions in small numbers of variables. A
nice algorithm due to G. Kabatiansky and C. Tavernier and improved and im-
plemented by Fourquet et al. [29,30,31,35,28] works well for
r
=2and
n
−
2
max
a∈F
2
|
W
f
(
a
)
|
≤
11 (
in some cases,
n
3, it is inecient, even for
n
= 8 (the number
of variables in the sub-S-boxes of the AES). No better algorithm is known.
Proving lower bounds on the
r
-th order nonlinearity of functions (and there-
fore proving their good behavior with respect to this criterion) is also a quite
dicult task, even for the second order. Until recently, there had been only one
≤
13). But for
r
≥
