New bounds for the nonlinearity of PN functions and APN functions over finite fields

The nonlinearity of a vectorial function over a finite field is defined in the paper as the Hamming distance from the function to the set of affine mappings in the space of values of all vectorial functions. For an arbitrary field of q elements we derive lower bounds for the nonlinearity of PN and APN functions in n variables in the form qn-qn-3 & sdot;2-2-2-1$ {q<^>n} - \sqrt {{q<^>n} - 3 \cdot {2<^>{ - 2}}} - {2<^>{ - 1}} $ and qn-2qn-7 & sdot;2-2-2-1$ {q<^>n} - \sqrt {2{q<^>n} - 7 \cdot {2<^>{ - 2}}} - {2<^>{ - 1}} $, respectively. These bounds improve the estimates obtained earlier in the Boolean case. It is shown that the nonlinearity of such functions can be estimated from above by qn - n - 1. For q = 2, 3, 4 the exact values of the nonlinearity of PN and APN functions of low dimension are obtained.