## 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.

### MSC:

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

Zbl 1366.94481

### Software:

SPECK; SIMECK; PICARO; SIMON
Full Text:

### References:

  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  Berlekamp, ER; Rumsey, H; Solomon, G, On the solution of algebraic equations over finite fields, Inf. Control., 12, 553-564, (1967) · Zbl 0166.04803  Biham, E; Shamir, A, Differential cryptanalysis of DES-like cryptosystems, J. Cryptol., 4, 3-72, (1991) · Zbl 0729.68017  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  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  Bracken, C; Tan, CH; Tan, Y, Binomial differentially 4-uniform permutations with high nonlinearity, Finite Fields Appl., 18, 537-546, (2012) · Zbl 1267.94043  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  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  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  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  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  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  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  Dillon, J.F.: Elementary Hadamard difference sets. Ph.D. Dissertation University of Maryland (1974) · Zbl 0346.05003  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)  Gold, R, Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inf. Theory, 14, 154-156, (1968) · Zbl 0228.62040  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  Knudsen, L.R., Robshaw, M.: The Block Cipher Companion. Springer (2011) · Zbl 1243.68010  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  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  Lai, X.: Higher Order Derivatives and Differential Cryptanalysis. Communications and Cryptography. Springer, 227-233 (1994) · Zbl 0840.94017  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  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)  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  Nyberg, K.: Perfect nonlinear S-boxes. In: Advances in Cryptology, EUROCRYPT’ 91. Lecture Notes in Computer Science, vol. 547, pp. 378-386. Springer (1992)  Nyberg, K; Knudsen, LR, Provable security against a differential attack, J. Cryptol., 8, 27-37, (1995) · Zbl 0817.94016  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)  Rothaus, OS, On bent functions, J. Combin. Theory Ser. A, 20, 300-305, (1976) · Zbl 0336.12012  Sidelnikov, VM, On the mutual correlation of sequences, Soviet Math. Dokl., 12, 197-201, (1971)  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  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)  Yu, Y; Wang, M; Li, Y, Constructing low differential uniformity functions from known ones, Chin. J. Electron., 22, 495-499, (2013)  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.