J Cryptogr Eng
make reference to the algebraic immunity extended to
Boolean vectorial functions (sometimes called “graph alge-
braic immunity”). This definition slightly varies from one
article to the next. Thus, we first remind the definition of the
algebraic immunity which we are going to use and we give
an algorithm to compute it (see [1,4,6,7,17,18,28]).
The algebraic immunity is defined as the lowest degree
of algebraic relations of a Boolean vectorial function. More
formally, let B : F
n
2
→ F
n
2
be a black box and I
B
⊂
F
2
[X
1
,...,X
n
, Y
1
,...,Y
n
] the ideal generated by the equa-
tions representing B and the field equations:
I
B
=S
B
∪ S
Field Eq.
Definition 1 The algebraic immunity of B is defined by
AI(B) = min{deg(P), P ∈ I
B
\ I
Field Eq.
}
Remark 1 The number of such lowest degree relations is also
an important invariant related to I
B
, and it is always com-
puted at the same time as the algebraic immunity.
To obtain the algebraic immunity of a black box B,we
could compute a Gröbner basis of I
B
with respect to a graded
order([4]):
Theorem 1 The reduced Gröbner basis G
B
of I
B
with
respect to a graded order contains a linear basis of the low-
est relations of B (i.e. the polynomials P ∈ I
B
such that
deg(P) = AI(B)).
Proof Every f ∈ I
B
is reduced to zero by a Gröbner
basis of I
B
. Thus, there is a polynomial g ∈ G
B
such that
the leading monomial LM(g) of g divides LM( f ).Aswe
have a graded monomial order, deg(g) = deg(LM(g)) and
deg( f ) = deg(LM( f )). Thus, deg(g) ≤ deg( f ) and we
prove that G
B
contains a linear generated family of the low-
est relations of B. Then the definition of a reduced Gröbner
basis implies that the linear generated family is a linearly
independent family.
Example 1 The algebraic immunity of the function calculat-
ing the inverse over F
2
8
(e.g. AES S-box) equals 2. Indeed,
the inverse function is represented by a set of 39 quadratic
equations over F
2
([23]) as well as over F
2
8
([7]).
2.2 Algebraic immunity of S-boxes with leakage
In the previous section, the concept of algebraic immunity
is defined as the lowest degree of algebraic relations of a
Boolean vectorial function. In the ASCA context, we are
looking for the lowest degree relations of B with leakage
information (e.g. Hamming weights, Hamming distances).
Therefore, we need to introduce a slightly different notion
of Algebraic Immunity to take the leakage into account. To
do so, for every value l of the leakage model, we consider
the ideal I
l
of F
2
[X
1
,...,X
n
, Y
1
,...,Y
n
] generated by the
equations representing B, the field equations S
Field Eq.
and by
L
l
the set of equations representing the leakage information
l, namely:
I
l
=S
B
∪ L
l
∪ S
Field Eq.
.
From this ideal we can define this new notion of algebraic
immunity.
Definition 2 Let B be a black box and l the value of the leak-
age model L.Thealgebraic immunity with leakage, denoted
by AI
L
(B, l), is defined by
AI
L
(B, l) = min{deg(P), P ∈ I
l
\ I
Field Eq.
}
The number of linearly independent relations in I
l
with
degree AI
L
(B, l) will be denoted by # AI
L
(B, l).
Similarly to the general notion of algebraic immunity, the
relations of lowest degree can be explicitly obtained by the
computation of a Gröbner basis of I
l
with respect to a graded
order (see [7]).
An other important invariant related to I
l
is the number of
points in the associated variety V (I
l
),i.e.thesetofcommon
roots of the polynomials in I
l
. This number which depends
on the black box B and on the value l of the leakage function
L, is also linked to our algebraic immunity with leakage and
it will be denoted by N
B
(l):
Definition 3 N
B
(l) is defined as the number of points of the
variety V(I
l
). In other words, N
B
(l) is equal to the cardinality
of the set {x ∈ F
n
2
s.t. L(x, B(x)) = l}
We will show in Sect.3 below that AI
L
(B, l) is equal to
1 in the cases of Hamming weight and Hamming distance
model. In this particular situation where AI
L
(B, l) is equal
to one (ie. there is at least one linear equation in the Ideal
I
l
), we prove the following relation between # AI
L
(B, l) and
N
B
(l):
Proposition 1 Let n be the bus size of B. If AI
L
(B, l) is
equal to 1 and N
B
(l) is non-zero then
N
B
(l) ≥ 2n + 1 − #AI
L
(B, l).
Proof As observed in Definition 3,wehaveN
B
(l) = #V (I
l
).
Since I
l
contains the field polynomials, it is radical. Its vari-
ety V (I
l
) is a subset of F
n
2
and, from the Nullstellensatz, we
have
#V (I
l
) = dim
F
2
[X
1
,...,X
n
, Y
1
,...,Y
n
]
I
l
= dim(Span(m
α
: α ∈ N
2n
, m
α
/∈ LT( I
l
)))
From this set of generating monomials, we only keep the set
F of monomials which have a degree less than or equal than
one:
F ={m : deg(m) ≤ 1andm /∈ LT( I
l
)}
123