DIFFERENTIALLY 4-UNIFORM FUNCTIONS 3 Proof. Suppose that (i) is true. Then we have x0 +x1 +x2 = α+x2 = x3 and so f(x0)+f(x1)+f(x2)+f(x0 +x1 +x2) = f(x0)+f(x1)+f(x2)+f(x3) = 0. The second equation holds true in the same way. Finally, we have x0 + x1 + x2 + x4 = x3 + x4 = 0. Conversely, let us set α = x0 + x1, β = f(x0) + f(x1) and x3 = α + x2 = x0 + x1 + x2. Then f(x2) + f(x3) = f(x2) + f(x0 + x1 + x2) = f(x0) + f(x1) = β. Furthermore, we have x3 = x0 because x1 = x2 and we have x3 = x1 since otherwise we would have x2 = α + x3 = α + x1 = x0. Setting x5 = α + x4 = x0 + x1 + x4 we have f(x4) + f(x5) = f(x4) + f(x0 + x1 + x4) = f(x0) + f(x1) = β. We have x3 = x4 since otherwise we would have 0 = x3 + x4 = x0 + x1 + x2 + x4 which is not the case by hypothesis. Finally x3 = x5 since otherwise we would have x2 = x4, and so all the six elements x0, x1, x2, x3, x4, x5 are different. We can now state a geometric characterization of differentially 4-uniform func- tions: Theorem 3. The differential uniformity of a function f : Fq −→ Fq is not larger than 4 if and only if: X(Fq) ⊂ V where X(Fq) denotes the set of rational points over Fq of X. Proof. The differential uniformity is not larger than 4 if and only if for any α ∈ Fq ∗ and any β ∈ Fq, the equation f(x + α) + f(x) = β has at most 4 solutions, that is to say {x ∈ Fq|f(x) + f(y) = β, x + y = α} ≤ 4. But this is equivalent to saying that we cannot find 6 distinct elements x0, x1, x2, x3, x4, x5 in Fq such that ⎧ ⎪x0 ⎨ ⎪ ⎩ + x1 = α, f(x0) + f(x1) = β x2 + x3 = α, f(x2) + f(x3) = β x4 + x5 = α, f(x4) + f(x5) = β. By the previous lemma, this is equivalent to saying that we cannot find 4 distinct elements x0, x1, x2, x4 in Fq such that x0 + x1 + x2 + x4 = 0 and such that f(x0) + f(x1) + f(x2) + f(x0 + x1 + x2) = 0 f(x0) + f(x1) + f(x4) + f(x0 + x1 + x4) = 0. But this can be reformulated by saying that the rational points over Fq of the variety X are contained in the variety V , that is to say X(Fq) ⊂ V . 3. Monomial functions with δ ≤ 4 If the function f is a monomial of degree d 3: f(x) = xd 3

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.