Information Technology Reference
In-Depth Information
a good behavior against fast algebraic attacks, see [1]. But the research in this
domain is active and better examples of functions will be found in the future. A
first one is available in [13].
The weight of a function
f
with given algebraic immunity satisfies the rela-
tion:
AI
(
f
)
−
1
i
=0
i
=0
i
. This shows that if
n
is odd and
f
has optimum algebraic immunity, then
f
is balanced. This has also led to
a bound on the first order nonlinearity by Dalai et al., which has been later
improved by Lobanov [42], who has obtained the tight lower bound:
nl
(
f
)
i
≤
≤
n−AI
(
f
)
wt
(
f
)
≥
i
=0
n−
i
.
In [11], a generalization of the Dalai et al. bound to the
r
-th
order nonlinearity has been derived:
nl
r
(
f
)
2
AI
(
f
)
−
2
i
=0
i
.In[8],another
bound has been obtained, which improves upon the bound of [11] for all values
of
AI
(
f
) when the number of variables is smaller than or equal to 12, and for
most values of
AI
(
f
) when the number of variables is smaller than or equal to 22
(which covers the practical situation of stream ciphers), and which also improves
asymptotically upon it:
nl
r
(
f
)
≥
AI
(
f
)
−r−
1
≥
max
r
≤n
(min (
λ
r
,μ
r
)), where:
⎛
⎞
⎠
n
i
,
n
r
−
AI
(
f
)
−
r
−
1
1
−
r
⎝
if
r
≤
λ
r
=2 max
AI
(
f
)
−
r
−
1
,
i
i
=0
i
=0
n
i
if
r
>AI
(
f
)
AI
(
f
)
−
r
−
1
=2
−
r
−
1
,
i
=0
n
+
n
.
r
AI
(
f
)
−
r
−
1
AI
(
f
)
−
r
+1
i
−
r
−
μ
r
=
i
i
=0
i
=0
Finally, S. Mesnager [46] has obtained a simpler bound, which improves upon
the bounds of [11] and [8] for low values of
r
(which play the most important
role for attacks):
n
i
+
n
.
AI
(
f
)
−
r
−
1
AI
(
f
)
−
r
−
1
−
r
nl
r
(
f
)
≥
i
i
=0
i
=
AI
(
f
)
−
2
r
These results have the interest of showing that,
automatically
, a function with
good algebraic immunity has not a very bad nonlinearity profile. However, all
the bounds above are rather weak with respect to the asymptotic bound (1).
A generalization to S-boxes.
The algebraic immunity of an (
n, m
)-function
F
can be defined as follows (see e.g. [2]). We call an annihilator of a subset
A
of
F
2
any
n
-variable Boolean function
g
whose restriction to
A
is null. We
denote by
An
k
(
A
) the vectorspace of annihilators of
A
of degrees at most
k
.
The algebraic immunity
AI
(
A
)of
A
equals the minimum algebraic degree of
all the nonzero annihilators of
A
and the algebraic immunity
AI
(
F
)of
F
is
the minimum algebraic immunity of all the sets
F
−
1
(
z
)=
F
2
/F
(
x
)=
z
{
x
∈
}
,
where
z
ranges over
F
2
(note that
AI
(
F
) equals 0 if and only if
F
is not onto
F
2
