Diﬀerentially 4-uniform functions
Yves Aubry and Fran¸ cois Rodier
Abstract. We give a geometric characterization of vectorial Boolean func-
tions with diﬀerential uniformity ≤ 4. This enables us to give a necessary
condition on the degree of the base ﬁeld for a function of degree
− 1 to be
We are interested in vectorial Boolean functions from the
to itself in m variables, viewed as polynomial functions f :
in one variable of degree at most
− 1. For a function f :
we consider, after K. Nyberg (see ), its diﬀerential uniformity
δ(f) = max
| f(x + α) + f(x) = β}.
This is clearly a strictly positive even integer.
Functions f with small δ(f) have applications in cryptography (see ). Such
functions with δ(f) = 2 are called almost perfect nonlinear (APN) and have been
extensively studied: see  and  for the genesis of the topic and more recently
 and  for a synthesis of open problems; see also  for new constructions and
 for a geometric point of view of diﬀerential uniformity.
Functions with δ(f) = 4 are also useful; for example the function x −→ x−1,
which is used in the AES algorithm over the ﬁeld
, has diﬀerential uniformity 4
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 diﬀerentially
4-uniform functions. We will show that for polynomial functions f of degree d =
− 1 such that δ(f) ≤ 4 on the ﬁeld
, 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.  to study cyclic codes and by A. Canteaut 
to show that certain power functions could not be APN when the exponent is too
2000 Mathematics Subject Classiﬁcation. 11R29,11R58,11R11,14H05.
Key words and phrases. Boolean functions, almost perfect nonlinear functions, varieties over
c 0000 (copyright holder)
Volume 521, 2010
c 2010 American Mathematical Society