Information Technology Reference
In-Depth Information
exchange large size data securely. The present paper is devoted to symmetric
cryptography and more precisely to the Boolean functions it often uses for mak-
ing the systems as nonlinear as possible, allowing them to resist known attacks
and hopefully future attacks. These are central objects for the design and the
security of symmetric cryptosystems (stream ciphers and block ciphers), see e.g.
[5,6]. In cryptography, the most usual representation of these functions is the
algebraic normal form
(ANF):
a
I
i∈I
f
(
x
1
,...,x
n
)=
x
i
,
I
⊆{
1
,...,n
}
where the
a
I
's are in
F
2
.Theterms
i∈I
x
i
are called
monomials
.The
algebraic
degree
d
◦
f
of a Boolean function
f
equals the global degree of its (unique) ANF,
that is, the maximum degree of those monomials whose coecients are nonzero.
Ane functions
are those Boolean functions of algebraic degrees at most 1.
The Boolean functions used in stream or block ciphers must have high degrees
to avoid the Berlekamp-Massey attack on stream ciphers and the higher order
differential cryptanalysis on block ciphers.
Another possible representation of Boolean functions uses the identification
between the vector-space
F
2
and the field
F
2
n
. It represents any Boolean func-
tion as a polynomial in one variable
x
F
2
n
of the form
f
(
x
)=
2
n
1
i
=0
f
i
x
i
,
where the
f
i
's are elements of the field. This representation exists for every func-
tion from
F
2
n
to
F
2
n
(this is easy to prove; note that the polynomial
2
n
−
∈
1
i
=0
f
i
x
i
can be obtained by using the so-called Mattson-Solomon polynomial [43,5])
and such function
f
is Boolean if and only if
f
0
and
f
2
n
−
1
belong to
F
2
and
f
2
i
=
f
i
−
=0
,
2
n
1, where 2
i
is taken mod 2
n
for every
i
−
−
1. This allows
representing
f
(
x
)intheform
k∈Γ
(
n
)
tr
n
k
(
f
k
x
k
)+
f
2
n
−
1
x
2
n
−
1
,where
Γ
(
n
)is
the set obtained by choosing one element in each cyclotomic class of 2 modulo
2
n
1 (the most usual choice for
k
is the smallest element in its cyclotomic
class, called the coset leader of the class), where
n
k
is the size of the cyclo-
tomic class containing
k
and where
tr
n
k
−
is the trace function from
F
2
n
k
to
F
2
:
tr
n
k
(
x
)=
x
+
x
2
+
x
2
2
+
+
x
2
n
k
−
1
. This representation is called the
trace rep-
resentation
.Notethat,forevery
k
···
∈
Γ
(
n
) and every
x
∈
F
2
n
,wehave
f
k
∈
F
2
n
k
(since
f
2
n
k
k
F
2
n
k
as well. A slightly different representation,
often called also the trace representation, has the form
f
(
x
)=
tr
(
2
n
=
f
k
)and
x
k
∈
1
i
=0
u
i
x
i
),
where
tr
=
tr
n
and where the
u
i
s
are elements of the field
F
2
n
(it can be easily
−
obtained from
f
(
x
)=
2
n
−
1
i
=0
f
i
x
i
since
f
(
x
)=
tr
(
λf
(
x
)), when
tr
(
λ
)=1).
The former representation is unique for every Boolean function and the latter is
not (see more e.g. in [5]). Recall that the 2-weight
w
2
(
i
) of an integer
i
equals
by definition the number of 1's in its binary expansion. The algebraic degree
of the function is then equal to the maximum 2-weight of the exponents
i
with
nonzero coecients
f
i
in the former representation and is upper bounded by the
maximum 2-weight of the exponents
i
with nonzero coecients
u
i
in the latter.
A characteristic of Boolean functions, called their nonlinearity profile, plays
an important role with respect to the security of the cryptosystems in which
they are involved. For every non-negative integer
r
≤
n
,wedenoteby
nl
r
(
f
)the
