Binomial differentially 4 uniform permutations with high nonlinearity (Q413555)

An \(S\)-box \(F\) is properly a permutation on the binary Galois field \(\mathbb{F}_{2^n}\), and it is highly nonlinear if it lies far, in terms of the Hamming distance, from the affine maps. The nonlinearity of a map can be characterized in terms of the Walsh spectrum of the map. The differential spectrum is the map \(\delta_F:(a,b)\mapsto \text{card}\{x\in\mathbb{F}_{2^n} \mid F(x+a)+F(x)=b\}\), and it is differentially \(r\)-uniform if \(\max_{(a,b)}\delta_F(a,b)\leq r\). In the context of stream ciphers, the involved \(S\)-boxes should be highly nonlinear and differentially \(r\)-uniform, with \(r\) very small, with the purpose to avoid linear and differential attacks. The smallest possible value for \(r\) is 2 and the maps attaining this value are called almost perfect nonlinear (APN). The search of APN maps has been quite extensive and several quadratic APN maps have been reported (see the references in the paper). For even \(n\), the multiplicative inverse map is differentially \(4\)-uniform, indeed this map is used in the cryptographic scheme AES. Several monomial maps, under certain conditions related to the degree of the Galois field, have also been reported as differentially \(4\)-uniform. In the current paper, the authors show a binomial (in the sense that it is expressed as the addition of two monomials) that determines a highly nonlinear, differentially \(4\)-uniform map, provided that some conditions on the degree of the field are satisfied. The authors show a first generalization of their binomial map, as another differentially \(4\)-uniform binomial, and they show other general construction of binomial differentially \(2^i\)-uniform maps. This is certainly a very first class of binomial maps with high nonlinearity. Finally, the authors pose an open problem consisting in proving that a given quadrinomial, proposed by themselves, is differentially \(2^i\)-uniform and highly nonlinear.