Binomial differentially 4 uniform permutations with high nonlinearity (Q413555): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q590981 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Guillermo Morales Luna / rank | |||
Normal rank |
Revision as of 02:08, 20 February 2024
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
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