Construction of new differentially <em>&delta;</em>-uniform families

Abstract

Our research work is on the construction of new differentially <em>&delta;</em>-uniform families of vectorial Boolean functions. Almost all of our families have explicit and compact univariate in a polynomial representation with very few terms whose coefficients are either in F₂ or are in a quadratic or cubic extension of it. Therefore they can be efficiently implemented in cryptographic applications. In addition, we have sub-families with high nonlinearity better than most of the differentially <em>&delta;</em>-uniform families recently discovered. That implies that they offer very good resistance to differential cryptanalysis. Given a differentially <em>&delta;</em>-uniform vectorial Boolean function <strong>F</strong>, we give a generalization of a well known theorem of Edel and Pott (based on the APN-switching method of Dillon) for APN functions to differential <em>&delta;</em>-uniform version. We introduce a new switching method for delta-uniform functions, so that from a vectorial Boolean function <strong>F</strong>, and another univariate Boolean function <em>f </em>and a vector <strong>u</strong>, we obtain all the switching neighbors of the form <strong>F </strong>+<strong> u ∙ f</strong> (generalizing quadratic switching APN functions of Budaghyan, Carlet and Leander). Our method gives us necessary and sufficient conditions so that these vectorial Boolean functions are differentially <em>&delta;</em>-uniform. As applications we obtain explicit families of the form stated.&nbsp;We also discover a new theorem for a dependent variable version of Edel and Dillon on APN function, which provides a different criterion. We algorithmically apply these new theorems to discover new <em>&delta;</em>-uniform and new APN functions. Also, another new theorem, with <em>(i, j)</em>-parameter families of functions, generalizes theorems of Budaghyan and Carlet, when we select <em>j </em>=<em> i</em>. This way, we also obtain new cubic APN functions. Different parameters generalize other known results and others yield new families with strong nonlinearity and algebraic degrees. Our functions offer strong resistance to both first and second order Fourier transform analysis (better than well known families, e.g. the Gold families). The remarkable result that the function x³ + tr(x⁹) is an APN function discovered by Budaghyan, Carlet, and Leander has not yet been generalized since 2008. Bracken, Byrne, Markin, and McGuire computed the Walsh spectrum of such a quadratic function. We give a generalization of that result.&nbsp;We obtain new families of functions generalizing a result of Budaghyan, by replacing a variable <em>v</em> by a polynomial <em>u(v)</em>. We give a variation of the idea of switching neighbor of Pott, and Pott-Budaghyan which yields further generalizations, leading to another new <em>&delta;</em>-uniform family of functions. We also give a second generalization of these results. Also, we formulate a narrow-sense switching technique along an axis. This technique helps us discover two elegant differentially <em>&delta;</em>-uniform families for each even <em>&delta;</em>.&nbsp;We include tables of the values of Walsh Spectrum and other cryptographic properties of the Gold family over finite fields up to degree 15. These include values that have not been computed by others. We thus show that there are cases where Gold families are weak with respect to some cryptographic protocols such as nonlinearity and algebraic multiplicity.&nbsp;Several authors have shown results on quadratic functions of the type tr(x^2a+1)+tr(x^2b+1) (Fitgerald, Lahtonen, McGuire and Ward). We open different directions, and give a lower bound for the nonlinearity of the family of functions <em>f</em>(x) = x^2k+1+(x^2k+x+1)tr(x^2k+1)tr(x^2j+1). We develop novel techniques to obtain such new families of functions. We apply our methods to study the Walsh spectrum and the nonlinearity profile of our families that are also applicable to families of functions that contain Boolean terms of the form tr(bx^2k+1).&nbsp;We give new differentially 4-uniform permutations in even degree field extension. Thus, we make a significant contribution to an open problem of Bracken and Leander (only a few results in this direction are known).