On Classification and Some Properties of APN Functions

Abstract

Boolean functions optimal with respect to different cryptographic properties (such as APN, AB, bent functions, etc.) are crucial to the design of secure cryptosystems. Investigating the properties and construction of these functions is therefore essential from both a theoretical and a practical point of view. In this thesis, we focus on the investigation of Almost Perfect Nonlinear (APN) functions, which provide optimal resistance against differential attack. Following a general overview of the cryptography background and the role of Boolean functions in cryptography, we give a systematic overview of different classes of cryptographically optimal Boolean functions and their characterizations and properties, and describe original results about the construction of new APN functions in some detail. In particular, we present an overview of our research concerning the existence of APN functions over F2n of algebraic degree n and a related construction involving changing the value of an existing APN function at a single point. We determine the Walsh spectra of the last three infinite quadratic APN families for which this had not been previously done. We give a table of representatives for all CCZinequivalent APN functions over the fields F2n for 6 ≤ n ≤ 11 which arise from all known families of APN functions. This table significantly facilitates the process of checking whether a given APN function is equivalent to any of the known infinite classes. We also present the results of an experimental procedure for classifying all quadratic APN polynomials of a particular form over fields of dimension 6 ≤ n ≤ 11.