Constructions with high algebraic degree of differentially 4-uniform (n, n − 1)-functions and differentially 8-uniform (n, n − 2)-functions

Quadratic differentially 4-uniform (n, n − 1)-functions are given in Carlet J. Adv. Math. Commun. 9(4), 541–565 (2015) where a question is raised of whether non-quadratic differentially 4-uniform (n, n − 1)-functions exist. In this paper, we give highly nonlinear differentially 4-uniform (n, n − 1)-functions of optimal algebraic degree for both n even and odd. Using the approach in Carlet J. Adv. Math. Commun. 9(4), 541–565 (2015), we construct these functions using two APN (n − 1, n − 1)-functions which are EA-equivalent Inverse functions satisfying some necessary and sufficient conditions when n is even. We slightly generalize the approach to construct differentially 4-uniform (n, n − 1)-functions from two differentially 4-uniform (n − 1, n − 1)-functions satisfying some necessary conditions. This allows us to derive the differentially 4-uniform (n, n − 1)-functions (x,xn)↦(xn+1)x2n−2+xnαx2n−2, x∈F2n−1, x_n∈ F₂, and α∈F2n−1∖F2, where Tr1n−1(α)=Tr1n−1(1α)=1. These (n, n − 1)-functions are balanced whatever the parity of n is and are then better suited for use as S-boxes in a Feistel cipher. We also give some properties of the Walsh spectrum of these functions to prove that they are CCZ-inequivalent to the differentially 4-uniform (n, n − 1)-functions of the form L ∘ F, where F is a known APN (n, n)-function and L is an affine surjective (n, n − 1)-function. Finally, we also give two new constructions of differentially 8-uniform (n, n − 2)-functions from EA-equivalent Cubic functions and from EA-equivalent Inverse functions.