Contemporary Mathematics
Differentially 4-uniform functions
Yves Aubry and Fran¸ cois Rodier
Abstract. We give a geometric characterization of vectorial Boolean func-
tions with differential uniformity 4. This enables us to give a necessary
condition on the degree of the base field for a function of degree
2r
1 to be
differentially 4-uniform.
1. Introduction
We are interested in vectorial Boolean functions from the
F2-vectorial
space
F2m
to itself in m variables, viewed as polynomial functions f :
F2m
−→
F2m
over the
field
F2m
in one variable of degree at most
2m
1. For a function f :
F2m
−→
F2m
,
we consider, after K. Nyberg (see [16]), its differential uniformity
δ(f) = max
α=0,β
{x
F2m
| f(x + α) + f(x) = β}.
This is clearly a strictly positive even integer.
Functions f with small δ(f) have applications in cryptography (see [16]). Such
functions with δ(f) = 2 are called almost perfect nonlinear (APN) and have been
extensively studied: see [16] and [9] for the genesis of the topic and more recently
[3] and [6] for a synthesis of open problems; see also [7] for new constructions and
[20] for a geometric point of view of differential uniformity.
Functions with δ(f) = 4 are also useful; for example the function x −→ x−1,
which is used in the AES algorithm over the field
F28
, has differential uniformity 4
on
F2m
for any even m. Some results on these functions have been collected by C.
Bracken and G. Leander [4, 5].
We consider here the class of functions f such that δ(f) 4, called differentially
4-uniform functions. We will show that for polynomial functions f of degree d =
2r
1 such that δ(f) 4 on the field
F2m
, the number m is bounded by an
expression depending on d. The second author demonstrated the same bound in
the case of APN functions [17, 18]. The principle of the method we apply here was
already used by H. Janwa et al. [13] to study cyclic codes and by A. Canteaut [8]
to show that certain power functions could not be APN when the exponent is too
large.
2000 Mathematics Subject Classification. 11R29,11R58,11R11,14H05.
Key words and phrases. Boolean functions, almost perfect nonlinear functions, varieties over
finite fields.
c 0000 (copyright holder)
1
Contemporary Mathematics
Volume 521, 2010
c 2010 American Mathematical Society
1
Previous Page Next Page