On properties of bent and almost perfect nonlinear functions

Abstract

(Vectorial) Boolean functions play an important role in all domains related to computer science, and in particular, in cryptography. The safety of a cryptosystem is quantified via some characteristics of (vectorial) Boolean functions implemented in it. The nonlinearity and differential uniformity are among the most important characteristics of cryptographic Boolean functions. Thus, bent and almost perfect nonlinear functions, which have the best possible nonlinearity and differential uniformity, respectively, are optimal cryptographic objects. This thesis is devoted to the investigation of the propertiesof these functions and is based on published articles.

In Paper I, a special subclass of bent Boolean functions, Niho bent functions, is studded. Boolean functions, and bent functions in particular, are considered up to the so-called EA-equivalence, which is the most general known equivalence relation preserving bentness. However, for Niho bent functions, there is a more general equivalence relation called o-equivalence, which is induced from the equivalence of o-polynomials (a special type of permutation polynomials). In this paper we study a group of transformations which generates all possible o-equivalent Niho bent functions from a given o-polynomial, and we exclude all transformations that never produce EA-inequivalent functions. We identify all cases which can potentially lead to pairwise EA-inequivalent Niho bent functions in a same o-equivalence class. For all known o-monomials, we identify the exact form of transformations which always lead to EA-inequivalent Niho bent functions. For o-polynomials, which are not monomials, we identify the exact form of transformations which can potentially lead to EA-inequivalent functions.

Paper II is devoted to the study of two long-standing open problems about APN power functions. The six infinite families of APN power functions are among the oldest known instances of APN functions. It was conjectured in 2000 that there does not exist any APN power function inequivalent to the known ones. This is the first long term open problem we study in Paper II. The functions affine equivalent to a power function have the form the composition of two linear transformations and the power function in between. This gives an idea to examine the composition of power functions with a linear function in between. So, we investigate such compositions , and show that some of the known APN power functions can be obtained from other known APN power functions through this construction. Moreover, we compute all APN functions of this form for n less or equal than 9 and for linear functions with binary coefficients, thereby confirming that our theoretical constructions exhaust all possible cases of known APN power functions. In addition, we present observations and data on power functions with exponents of the special form defined over the field of the dimension mk which generalize the inverse and the Dobbertin families of APN power functions.

Another long-standing open problem is the Walsh spectrum of the Dobbertin APN power family. In Paper II, we derive alternative representations for some of the known families of APN monomials. We show that the Niho and Dobbertin functions can be represented as the composition of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can produce the same composition. We show as well that the exponents of the Welch functions are optimal in this sense. Based on a computational data performed for n less or equal than 35, we present a conjecture depending on the parity of n, which wholly describes the Walsh spectrum of the Dobbertin functions.

In Paper III, we generalize an infinite family of APN binomials, for n divisible by 4 behaves exactly as the Gold function in respect to their differential uniformity, the size of the image space and being permutations.