Information Technology Reference
In-Depth Information
and that, if
F
is surjective and if there exists
z
such that
F
−
1
(
z
)isasingleton-
if
F
is a permutation, for instance - then
AI
(
F
) equals 1; other generalizations
of the notion of algebraic immunity to S-boxes can be given, which correspond
to diverse variants of algebraic attacks, see e.g. [2]). Note that, for every
z
∈
F
2
,
i
=0
i
since otherwise there would exist a nonzero
annihilator of degree at most
AI
(
F
)
|≥
AI
(
F
)
−
1
F
−
1
(
z
)
we have
|
1of
F
−
1
(
z
), a contradiction (indeed, a
function is a nonzero annihilator of degree at most
AI
(
F
)
−
1of
F
−
1
(
z
)ifand
only if the coecients in its ANF constitute a non-trivial solution of a system
of
−
i
=0
i
then this system must have a non-trivial solution). This property will be used
in the proof of Theorem 1 below.
The results of [8] and [46] nicely generalize to S-boxes. We give in Proposition 2
below a lower bound on the size of the intersection between a set of a given
algebraic immunity and the support of a function of given algebraic degree,
which is a straightforward adaptation of several lemmas of these two papers. We
deduce in Theorem 1 the generalization to S-boxes of the bounds of [8] and [46].
i
variables and if
equations in
AI
(
F
)
−
1
i
=0
<
AI
(
F
)
−
1
F
−
1
(
z
)
F
−
1
(
z
)
|
|
|
|
Proposition 2.
Let
A
be a subset of
F
2
and let
r
be a positive integer and
r
a
non-negative integer such that
r
≤
0
. For every
n
-variable
Boolean function
h
of degree
r
and of algebraic immunity
r
, we have:
r
and
AI
(
A
)
−
r
−
1
≥
⎛
⎞
⎠
n
i
,
n
r
−
AI
(
A
)
−r−
1
1
−
r
⎝
if
r
≤
|
A
∩
supp
(
h
)
|≥
max
AI
(
A
)
−
r
−
1
,
i
i
=0
i
=0
n
i
if
r
>AI
(
A
)
AI
(
A
)
−
r
−
1
≥
−
r
−
1
,
i
=0
where
supp
(
h
)
denotes the support of
h
,and:
dim
Mul
AI
(
A
)
−r−
1
(
h
)
,
where
Mul
AI
(
A
)
−r−
1
(
h
)
is the set of all products of
h
with functions of degrees
at most
AI
(
A
)
dim
An
AI
(
A
)
−
1
(
supp
(
h
+1))
≥
|
A
∩
supp
(
h
)
|≥
−
r
−
1
. In all cases, we have:
n
.
AI
(
A
)
−r−
1
−
r
|
A
∩
supp
(
h
)
|≥
i
i
=0
Proof.
Let
k
be any non-negative integer. A Boolean function of degree at most
k
belongs to
An
k
(
A
supp
(
h
)) if and only if the coecients in its ANF satisfy a
system of
|A ∩ supp
(
h
)
|
equations in
i
=0
i
variables (the coecients of the
monomials of degrees at most
k
in the ANF of the function). Hence we have:
dim(
An
k
(
A
∩
≥
i
=0
i
−|
∩
supp
(
h
)))
A
∩
supp
(
h
)
|
.
AccordingtoLemma1of[8],wehave:
min
.
n
i
,
n
i
n
k
k
k
−
r
dim(
An
k
(
supp
(
h
)))
≤
−
i
i
=
r
i
=0
i
=0
