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 Volume 521, 2010 c 2010 American Mathematical http://dx.doi.org/10.1090/conm/521/10268

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.