Bounds on the degree of APN polynomials: the case of \(x^{-1} + g(x)\) (Q2430690): Difference between revisions

The paper under review deals with functions \(f : {\mathbb F}_{2^m}\rightarrow {\mathbb F}_{2^m}\) given by their polynomial representation. Such a function is called almost perfect nonlinear (APN) if for every non-zero \(a\in {\mathbb F}_{2^m}\) and every \(b \in {\mathbb F}_{2^m}\) the equation \(f(x)+f(x+a)=b\) admits at most two solutions \(x\in {\mathbb F}_{2^m}\). Such functions are particularly interesting for symmetric cryptography. The authors consider APN functions of the form \(f(x) = x^{-1}+g(x)\), where \(g(x)\) is any non-\({\mathbb F}_{2}\)-affine polynomial. They give a lower bound on the degree of \(g(x)\) which yields that such a function \(f\) is APN on at most a finite number of fields \( {\mathbb F}_{2^m}\). Moreover, they prove that if \(\deg g(x) \leq 6\), then functions of the above form are APN only in the case where \(m \leq 3\) and are equivalent to \(x^3\).