Contemporary Mathematics

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

2r

− 1 to be

diﬀerentially 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

ﬁeld

F2m

in one variable of degree at most

2m

− 1. For a function f :

F2m

−→

F2m

,

we consider, after K. Nyberg (see [16]), its diﬀerential 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 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

F28

, has diﬀerential 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 diﬀerentially

4-uniform functions. We will show that for polynomial functions f of degree d =

2r

− 1 such that δ(f) ≤ 4 on the ﬁeld

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 Classiﬁcation. 11R29,11R58,11R11,14H05.

Key words and phrases. Boolean functions, almost perfect nonlinear functions, varieties over

ﬁnite ﬁelds.

c 0000 (copyright holder)

1

Contemporary Mathematics

Volume 521, 2010

c 2010 American Mathematical Society

1

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

2r

− 1 to be

diﬀerentially 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

ﬁeld

F2m

in one variable of degree at most

2m

− 1. For a function f :

F2m

−→

F2m

,

we consider, after K. Nyberg (see [16]), its diﬀerential 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 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

F28

, has diﬀerential 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 diﬀerentially

4-uniform functions. We will show that for polynomial functions f of degree d =

2r

− 1 such that δ(f) ≤ 4 on the ﬁeld

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 Classiﬁcation. 11R29,11R58,11R11,14H05.

Key words and phrases. Boolean functions, almost perfect nonlinear functions, varieties over

ﬁnite ﬁelds.

c 0000 (copyright holder)

1

Contemporary Mathematics

Volume 521, 2010

c 2010 American Mathematical Society

1