zbMATH — the first resource for mathematics

Binomial differentially 4 uniform permutations with high nonlinearity. (English) Zbl 1267.94043
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.

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14G50 Applications to coding theory and cryptography of arithmetic geometry
Full Text: DOI
[1] T. Beth, C. Ding, On almost perfect nonlinear permutations, in: EUROCRYPT, 1993, pp. 65-76. · Zbl 0951.94524
[2] Bierbrauer, J., New semifields, PN and APN functions, Des. codes cryptogr., 54, 3, 189-200, (2010) · Zbl 1269.12006
[3] Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. cryptology, 4, 1, 3-72, (1991) · Zbl 0729.68017
[4] Bracken, C.; Byrne, E.; Markin, N.; McGuire, G., Determining the nonlinearity of a new family of APN functions, (), 72-79 · Zbl 1195.94048
[5] Bracken, C.; Byrne, E.; Markin, N.; McGuire, G., New families of quadratic almost perfect nonlinear trinomials and multinomials, Finite fields appl., 14, 3, 703-714, (2008) · Zbl 1153.11058
[6] Bracken, C.; Byrne, E.; Markin, N.; McGuire, G., A few more quadratic APN functions, Cryptogr. commun., 1-11, (2010)
[7] Bracken, C.; Leander, G., A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree, Finite fields appl., 16, 4, 231-242, (2010) · Zbl 1194.94182
[8] Budaghyan, L.; Carlet, C.; Leander, G., Two classes of quadratic APN binomials inequivalent to power functions, IEEE trans. inform. theory, 54, 9, 4218-4229, (2008) · Zbl 1177.94135
[9] Budaghyan, L.; Carlet, C.; Pott, A., New classes of almost bent and almost perfect nonlinear polynomials, IEEE trans. inform. theory, 52, 3, 1141-1152, (2006) · Zbl 1177.94136
[10] Carlet, C., Vectorial Boolean functions for cryptography, (), 398-471 · Zbl 1209.94036
[11] J.F. Dillon, Almost perfect nonlinear polynomials: An update, In: 9th International Conference on Finite Fields and Applications Fq9, Dublin, Ireland, 2009.
[12] Dobbertin, H., One-to-one highly nonlinear power functions on \(\operatorname{GF}(2^n)\), Appl. algebra engrg. comm. comput., 9, 2, 139-152, (1998) · Zbl 0924.94026
[13] Gold, R., Maximal recursive sequences with 3-valued recursive cross-correlation functions (corresp.), IEEE trans. inform. theory, 14, 1, 154-156, (Jan. 1968)
[14] Kasami, T., The weight enumerators for several clauses of subcodes of the 2nd order binary Reed-muller codes, Inf. control, 18, 4, 369-394, (1971) · Zbl 0217.58802
[15] Matsui, M., Linear cryptanalysis method for DES cipher, (), 386-397 · Zbl 0951.94519
[16] Nyberg, K., Differentially uniform mappings for cryptography, (), 55-64 · Zbl 0951.94510
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.