Constructions with high algebraic degree of differentially 4-uniform \((n, n - 1)\)-functions and differentially 8-uniform \((n, n - 2)\)-functions. (English) Zbl 1382.11093

Summary: Quadratic differentially 4-uniform \((n, n - 1)\)-functions are given in [C. Carlet and Y. Alsalami, Adv. Math. Commun. 9, No. 4, 541–565 (2015; Zbl 1366.94481)] where a question is raised of whether non-quadratic differentially 4-uniform \((n, n - 1)\)-functions exist. In this paper, we give highly nonlinear differentially 4-uniform \((n, n - 1)\)-functions of optimal algebraic degree for both \(n\) even and odd. Using the approach in [loc. cit.], we construct these functions using two APN \((n - 1, n - 1)\)-functions which are EA-equivalent Inverse functions satisfying some necessary and sufficient conditions when \(n\) is even. We slightly generalize the approach to construct differentially 4-uniform \((n, n - 1)\)-functions from two differentially 4-uniform \((n - 1, n - 1)\)-functions satisfying some necessary conditions. This allows us to derive the differentially 4-uniform \((n, n - 1)\)-functions \((x,x_{n})\mapsto (x_{n}+1)x^{2^{n}-2}+x_{n} \alpha x^{2^{n}-2}\), \(x \in \mathbb{F}_{2^{n-1}}\), \(x_{n}\in \mathbb {F}_{2}\), and \(\alpha \in \mathbb {F}_{2^{n-1}}\setminus \mathbb{F}_{2}\), where \(\mathrm{Tr}_{1}^{n-1}(\alpha )=\mathrm{Tr}_{1}^{n-1}(\frac {1}{\alpha })=1\). These \((n, n - 1)\)-functions are balanced whatever the parity of \(n\) is and are then better suited for use as S-boxes in a Feistel cipher. We also give some properties of the Walsh spectrum of these functions to prove that they are CCZ-inequivalent to the differentially 4-uniform \((n, n - 1)\)-functions of the form \(L\) \(F\), where \(F\) is a known APN \((n, n)\)-function and \(L\) is an affine surjective \((n, n - 1)\)-function. Finally, we also give two new constructions of differentially 8-uniform \((n, n - 2)\)-functions from EA-equivalent Cubic functions and from EA-equivalent Inverse functions.


11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography
94D10 Boolean functions


Zbl 1366.94481


Full Text: DOI


[1] Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK Families of Lightweight Block Ciphers. Cryptology ePrint Archive Report 2013/404 (2013) · Zbl 1382.94059
[2] Berlekamp, ER; Rumsey, H; Solomon, G, On the solution of algebraic equations over finite fields, Inf. Control., 12, 553-564, (1967) · Zbl 0166.04803
[3] Biham, E; Shamir, A, Differential cryptanalysis of DES-like cryptosystems, J. Cryptol., 4, 3-72, (1991) · Zbl 0729.68017
[4] Blondeau, C., Nyberg, K.: Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities. In: EUROCRYPT 2014. Lecture Notes in Computer Science, vol. 8441, pp. 165-182 (2014) · Zbl 1332.94060
[5] Bracken, C; Leander, G, A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree, Finite Fields Appl., 16, 231-242, (2010) · Zbl 1194.94182
[6] Bracken, C; Tan, CH; Tan, Y, Binomial differentially 4-uniform permutations with high nonlinearity, Finite Fields Appl., 18, 537-546, (2012) · Zbl 1267.94043
[7] Canteaut, A; Charpin, P; Dobbertin, H, Weight divisibility of cyclic codes, highly nonlinear functions on \(G\)\(F\)(2\^{}{\(m\)}, ) and crosscorrelation of maximum- length sequences, SIAM J. Discret. Math., 13, 105-138, (2000) · Zbl 1010.94013
[8] Carlet, C, Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions, Des. Codes Crypt., 59, 89-109, (2011) · Zbl 1229.94041
[9] Carlet, C.: On known and new differentially uniform functions. In: Proceedings of Information Security and Privacy - 16th Australasian Conference (ACISP) 2011, Melbourne, pp. 1-15 (2011) · Zbl 1279.94060
[10] Carlet, C., Alsalami, Y.: A New construction of differentially 4-uniform (\(n\), \(n\) − 1)-functions. J. Adv. Math. Commun. 9(4), 541-565 (2015) · Zbl 1366.94481
[11] Carlet, C; Charpin, P; Zinoviev, V, Codes, bent bunctions and permutations suitable for DES-like cryptosystems, Des. Codes Crypt., 15, 125-156, (1998) · Zbl 0938.94011
[12] Carlet, C., Tang, D., Tang, X., Liao, Q.: New construction of differentially 4-uniform bijections. In: Information Security and Cryptology, pp. 22-38. Springer (2014) · Zbl 1347.94024
[13] Chabaud, F., Vaudenay, S., differential: Links between differential and linear cryptanalysis. In: EUROCRYPT94, Advances in Cryptology. Lecture Notes in Computer Science, vol. 950, pp. 356-365. Springer (1995) · Zbl 0879.94023
[14] Dillon, J.F.: Elementary Hadamard difference sets. Ph.D. Dissertation University of Maryland (1974) · Zbl 0346.05003
[15] Dobbertin, H.: Almost perfect nonlinear power functions on \(G\)\(F\)(2\^{}{\(n\)}): a new case for n divisible by 5. In: Proceedings of Finite Fields and Applications \(F\)\(q\)5, pp. 113-121. Springer, Augsburg (2000)
[16] Gold, R, Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inf. Theory, 14, 154-156, (1968) · Zbl 0228.62040
[17] Kasami, T, The weight enumerators for several classes of subcodes of the second order binary Reed-muller codes, Inf. Control., 18, 369-394, (1971) · Zbl 0217.58802
[18] Knudsen, L.R., Robshaw, M.: The Block Cipher Companion. Springer (2011) · Zbl 1243.68010
[19] Knudsen, L.R.: Truncated and higher order differentials. In: Proceedings of Fast Software Encryption Second International Workshop. Lecture Notes in Computer Science, vol. 1008, pp. 196-211 (1995) · Zbl 0939.94556
[20] Lachaud, G; Wolfmann, J, The weights of the orthogonals of the extended quadratic binary Goppa codes, IEEE Trans. Inform. Theory, 36, 686-692, (1990) · Zbl 0703.94011
[21] Lai, X.: Higher Order Derivatives and Differential Cryptanalysis. Communications and Cryptography. Springer, 227-233 (1994) · Zbl 0840.94017
[22] Matsui, M.: Linear cryptanalysis method for des cipher. In: Advances in Cryptology - EUROCRYPT’93, no. 765. Lecture Notes in Computer Science, pp. 386-397. Springer (1994) · Zbl 0951.94519
[23] National Institute of Standards and Technology: Advanced encryption standard (AES). Federal Information Processing Standards Publication 197 United States National Institute of Standards and Technology (NIST) (2001)
[24] National Institute of Standards and Technology: Data Encryption Standard (DES). Federal Information Processing Standards Publication 49-3. United States National Institute Of Standards And Technology (NIST) Reaffirmed on October 25, 1999
[25] Nyberg, K.: Perfect nonlinear S-boxes. In: Advances in Cryptology, EUROCRYPT’ 91. Lecture Notes in Computer Science, vol. 547, pp. 378-386. Springer (1992)
[26] Nyberg, K; Knudsen, LR, Provable security against a differential attack, J. Cryptol., 8, 27-37, (1995) · Zbl 0817.94016
[27] Piret, G., Roche, T., Carlet, C.: PICARO - a block cipher allowing efficient higher-order side-channel resistance. In: Proceedings of 10th International Conference in Applied Cryptography and Network Security 2012. Lecture Notes in Computer Science, vol. 7341, pp. 311-328 (2012)
[28] Rothaus, OS, On bent functions, J. Combin. Theory Ser. A, 20, 300-305, (1976) · Zbl 0336.12012
[29] Sidelnikov, VM, On the mutual correlation of sequences, Soviet Math. Dokl., 12, 197-201, (1971)
[30] Tan, Y; Qu, L; Tan, C; Li, C; Helleseth, T (ed.); Jedwab, J (ed.), New families of differentially 4-uniform permutations over \(\mathbb{F}_{2^{2k}}\), 25-39, (2012), Heidelberg · Zbl 1290.94034
[31] Xu, G., Cao, X., Xu, S.: Constructing New Differentially 4-Uniform Permutations and APN Functions over Finite fields. Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences. Pre-print (2014)
[32] Yu, Y; Wang, M; Li, Y, Constructing low differential uniformity functions from known ones, Chin. J. Electron., 22, 495-499, (2013)
[33] Zha, Z; Hu, L; Sun, S, Constructing new differentially 4-uniform permutations from the inverse function, Finite Fields Appl., 25, 64-78, (2014) · Zbl 1305.94084
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.