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

We introduce a new concept, the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">APN-defect</i>, which can be thought of as measuring the distance of a given function <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$G:\mathbb {F}_{2^{n}} \rightarrow \mathbb {F}_{2^{n}}$ </tex-math></inline-formula> 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) <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</i> using the so-called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">difference squares</i>. 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">quasi-APN</i> 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{2^{n}}$ </tex-math></inline-formula> and present quantitative results on their differential behaviour.