Analysis of Functions of Low Differential Uniformity in Characteristic 2: A New Approach (I)

We introduce a new concept, the APN-defect, which can be thought of as measuring the distance of a given function G : F-2(n) -> F-2(n) to the set of almost perfect nonlinear (APN) functions. This concept is motivated by the detailed analysis of the differential behaviour of non-APN functions (of low differential uniformity) G using the so-called difference squares. Indeed, the insight into some structural qualities of S-boxes provided by this new approach is particularly useful in the light of recent refinements of differential cryptanalysis. We describe the relations between the APN-defect and other current concepts of similar nature. Values of APN-defect for several classes of functions of interest, including Dembowski-Ostrom polynomials are given. This enables one to identify the quasi-APN ones, i.e., those with favourable differential behavior. The difference square corresponding to a modification of the inverse function is determined, its APN-defect depending on n is evaluated, the partial quadruple system associated to it is described, and the implications are discussed. In the forthcoming second part of this work we further examine the APN-defect of modifications of the inverse function and address some questions concerning CCZ-equivalence. We also study modifications of classes of functions of low differential uniformity over infinitely many extensions of F-2(n) and present quantitative results on their differential behaviour.