Binomial differentially 4 uniform permutations with high nonlinearity (Q413555)

From MaRDI portal
Revision as of 02:08, 20 February 2024 by RedirectionBot (talk | contribs) (‎Removed claim: reviewed by (P1447): Item:Q590981)
scientific article
Language Label Description Also known as
English
Binomial differentially 4 uniform permutations with high nonlinearity
scientific article

    Statements

    Binomial differentially 4 uniform permutations with high nonlinearity (English)
    0 references
    0 references
    0 references
    0 references
    7 May 2012
    0 references
    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.
    0 references
    almost perfect nonlinear function
    0 references
    APN function
    0 references
    differentially 4-uniform function
    0 references
    permutation polynomial
    0 references
    quadratic function
    0 references

    Identifiers