On functions of low differential uniformity in characteristic 2: A close look (I)

We introduce a new concept, the APN-defect, which can be thought of as measuring the distance of a given function $G:\mathbb{F}_{2^n} \rightarrow \mathbb{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. We describe the relations between the APN-defect and other recent concepts of similar nature. Upper and lower bounds for the values of APN-defect for several classes of functions of interest, including Dembowski-Ostrom polynomials are given. Its exact values in some cases are also calculated. The difference square corresponding to a modification of the inverse function is determined, its APN-defect depending on $n$ is evaluated and the implications are discussed. In the forthcoming second part of this work we further examine modifications of the inverse function. We also study modifications of classes of functions of low uniformity over infinitely many extensions of $\mathbb{F}_{2^n}$. We present quantitative results on their differential behaviour, especially in connection with their APN-defects.
Comment: 33 pages, 1 table (the table is not separate, it is included in the tex file))