# American Institute of Mathematical Sciences

November  2015, 9(4): 541-565. doi: 10.3934/amc.2015.9.541

## A new construction of differentially 4-uniform $(n,n-1)$-functions

 1 Department of Mathematics, LAGA, University of Paris 8, (and LAGA, University of Paris 13, CNRS), France 2 Department of Computer Engineering, Khalifa University of Science, Technology and Research, United Arab Emirates

Received  May 2014 Revised  January 2015 Published  November 2015

In this paper, a new way to construct differentially 4-uniform $(n,n-1)$-functions is presented. As APN $(n,n)$-functions, these functions offer the best resistance against differential cryptanalysis and they can be used as substitution boxes in block ciphers with a Feistel structure. Constructing such functions is assumed to be as difficult as constructing APN $(n,n)$-functions. A function in our family of functions can be viewed as the concatenation of two APN $(n-1,n-1)$-functions satisfying some necessary conditions. Then, we study the special case of this construction in which the two APN functions differ by an affine function. Within this construction, we propose a family in which one of the APN functions is a Gold function which gives the quadratic differentially 4-uniform $(n,n-1)$-function $(x,x_n)\mapsto x^{2^i+1}+x_n x$ where $x\in \mathbb{F}_{2^{n-1}}$ and $x_n\in \mathbb{F}_2$ with $\gcd(i,n-1)=1$. We study the nonlinearity of this function in the case $i=1$ because in this case we can use results from Carlitz which are unknown in the general case. We also give the Walsh spectrum of this function and prove that it is CCZ-inequivalent to functions of the form $L \circ F$ where $L$ is an affine surjective $(n,n-1)$-function and $F$ is a known APN $(n,n)$-function for $n\leq 8$, or the Inverse APN $(n,n)$-function for every $n\geq 5$ odd, or any AB $(n,n)$-function for every $n>3$ odd, or any Gold APN $(n,n)$-function for every $n>4$ even.
Citation: Claude Carlet, Yousuf Alsalami. A new construction of differentially 4-uniform $(n,n-1)$-functions. Advances in Mathematics of Communications, 2015, 9 (4) : 541-565. doi: 10.3934/amc.2015.9.541
##### References:
 [1] C. M. Adams, Constructing symmetric ciphers using the CAST design procedure,, Designs, 12 (1997), 283.  doi: 10.1023/A:1008229029587.  Google Scholar [2] R. Anderson, E. Biham and L. Knudsen, Serpent: A proposal for the Advanced Encryption Standard,, National Institute of Standards and Technology AES Proposal, 174 (1998).   Google Scholar [3] T. Beth and C. Ding, On almost perfect nonlinear permutations,, Advances in Cryptology-EUROCRYPT'93, 765 (1993), 65.  doi: 10.1007/3-540-48285-7_7.  Google Scholar [4] E. Biham, R. Anderson and L. Knudsen, Serpent: A new block cipher proposal,, Fast Software Encryption, 1372 (1998), 222.  doi: 10.1007/3-540-69710-1_15.  Google Scholar [5] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems,, Journal of Cryptology, 4 (1991), 3.  doi: 10.1007/BF00630563.  Google Scholar [6] C. Blondeau and K. Nyberg, Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities,, EUROCRYPT 2014, 8441 (2014), 165.  doi: 10.1007/978-3-642-55220-5_10.  Google Scholar [7] M. Brinkmann and G. Leander, On the classification of APN functions up to dimension five,, Designs, 49 (2008), 273.  doi: 10.1007/s10623-008-9194-6.  Google Scholar [8] K. Browning, J. F. Dillon, M. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six,, Contemporary Mathematics, 518 (2010), 33.  doi: 10.1090/conm/518/10194.  Google Scholar [9] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin and C. Vikkelsoe, PRESENT: An Ultra-Lightweight Block Cipher,, CHES 2007, 4727 (2007), 450.  doi: 10.1007/978-3-540-74735-2_31.  Google Scholar [10] L. Budaghyan and C. Carlet, CCZ-equivalence of single and multi output Boolean functions,, AMS Contemporary Math., 518 (2010), 43.  doi: 10.1090/conm/518/10195.  Google Scholar [11] L. Budaghyan, C. Carlet and T. Helleseth, On bent functions associated to AB functions,, IEEE Information Theory Workshop, (2011), 150.  doi: 10.1109/ITW.2011.6089365.  Google Scholar [12] C. Bracken and G. Leander, A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree,, Finite Fields and Their Applications, 16 (2010), 231.  doi: 10.1016/j.ffa.2010.03.001.  Google Scholar [13] C. Bracken, C. H. Tan and Y. Tan, Binomial differentially 4-uniform permutations with high nonlinearity,, Finite Fields Applications, 18 (2012), 537.  doi: 10.1016/j.ffa.2011.11.006.  Google Scholar [14] C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems,, Designs, 15 (1998), 125.  doi: 10.1023/A:1008344232130.  Google Scholar [15] C. Carlet, Vectorial boolean functions for cryptography,, Chapter of the monography Boolean Models and Methods in Mathematics, (2010), 398.  doi: 10.1017/CBO9780511780448.012.  Google Scholar [16] C. Carlet, On known and new differentially 4-uniform functions,, Proceedings of the 16th Australisian Conference on Information Security and Privacy (ACISP) 2011, 6812 (2011), 1.  doi: 10.1007/978-3-642-22497-3_1.  Google Scholar [17] L. Carlitz, Explicit evaluation of certain exponential sums,, In Math. Scand., 44 (1979), 5.   Google Scholar [18] P. Charpin, T. Helleseth and V. A. Zinoviev, The divisibility modulo 24 of Kloosterman sums on $GF(2^m)$, $m$ odd,, Journal of Combinatorial Theory, 114 (2007), 322.  doi: 10.1016/j.jcta.2006.06.002.  Google Scholar [19] F. Chabaud and S. Vaudenay, Links between differential and linear cryptanalysis,, EUROCRYPT'94, 950 (1995), 356.  doi: 10.1007/BFb0053450.  Google Scholar [20] J. Daemen and V. Rijmen, The Design of Rijndael: AES: The Advanced Encryption Standard,, Springer, (2002).  doi: 10.1007/978-3-662-04722-4.  Google Scholar [21] J. F. Dillon, Elementary Hadamard Difference Sets,, Ph.D. Dissertation. University of Maryland, (1974).   Google Scholar [22] H. Dobbertin, Almost perfect nonlinear power functions over GF($2^n$): The Niho case,, Information and Computation, 151 (1999), 57.  doi: 10.1006/inco.1998.2764.  Google Scholar [23] H. Dobbertin, Almost perfect nonlinear power functions over GF($2^n$): The Welch case,, IEEE Transactions on Information Theory, 45 (1999), 1271.  doi: 10.1109/18.761283.  Google Scholar [24] H. Dobbertin, Almost perfect nonlinear power functions on $GF(2^n)$: a new case for $n$ divisible by 5,, Proceedings of Finite Fields and Applications Fq5, (2001), 113.   Google Scholar [25] European Telecommunications Standards Institute, Technical Specification 135 202 V9.0.0: Universal mobile telecommunications system (UMTS); LTE;, specification of the 3GPP confidentiality and integrity algorithms; Document 2: KASUMI specification (3GPP TS 35.202 V9.0.0 Release 9)., ().   Google Scholar [26] R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions,, IEEE Transactions on Information Theory, 14 (1968), 154.  doi: 10.1109/TIT.1968.1054106.  Google Scholar [27] S. Hu, S. Li, T. Zhang, T. Feng and G. Ge, New pseudo-planar binomials in characteristic two and related schemes,, Designs, 76 (2015), 345.  doi: 10.1007/s10623-014-9958-0.  Google Scholar [28] T. Kasami, The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes,, Information and Control, 18 (1971), 369.  doi: 10.1016/S0019-9958(71)90473-6.  Google Scholar [29] L. R. Knudsen and M. Robshaw, The Block Cipher Companion,, Springer, (2011).  doi: 10.1007/978-3-642-17342-4.  Google Scholar [30] L. R. Knudsen, Truncated and higher order differentials,, Proceedings of Fast Software Encryption, 1008 (2005), 196.  doi: 10.1007/3-540-60590-8_16.  Google Scholar [31] G. Lachaud and J. Wolfmann, The weights of the orthogonals of the extended quadratic binary Goppa codes,, IEEE Transactions on Information Theory, 36 (1990), 686.  doi: 10.1109/18.54892.  Google Scholar [32] G. Leander and A. Poschmann, On the classification of 4 Bit S-boxes,, WAIFI 2007. Lecture Notes in Computer Science, 4547 (2007), 159.  doi: 10.1007/978-3-540-73074-3_13.  Google Scholar [33] M. Matsui, Block encryption algorithm MISTY,, Fast Software Encryption, 1267 (1997), 54.  doi: 10.1007/BFb0052334.  Google Scholar [34] M. Matsui, Linear cryptanalysis method for DES cipher,, Advances in Cryptology - EUROCRYPT'93, 765 (2001), 386.  doi: 10.1007/3-540-48285-7_33.  Google Scholar [35] 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).   Google Scholar [36] 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), 49.   Google Scholar [37] K. Nyberg, Perfect nonlinear S-boxes,, Advances in Cryptology, 547 (1991), 378.  doi: 10.1007/3-540-46416-6_32.  Google Scholar [38] K. Nyberg, S-boxes and round functions with controllable linearity and differential uniformity,, Fast Software Encryption (FSE'94), 1008 (1995), 111.  doi: 10.1007/3-540-60590-8_9.  Google Scholar [39] K. Nyberg and L. R. Knudsen, Provable security against differential cryptanalysis,, Proceedings of CRYPT0'92, 740 (1993), 566.  doi: 10.1007/3-540-48071-4_41.  Google Scholar [40] K. Nyberg and L. R. Knudsen, Provable security against a differential attack,, Journal of Cryptology, 8 (1995), 27.  doi: 10.1007/BF00204800.  Google Scholar [41] G. Piret, T. Roche and C. Carlet, PICARO - A block cipher allowing efficient higher-order side-channel resistance,, Proceedings of 10th International Conference in Applied Cryptography and Network Security 2012, 7341 (2012), 311.  doi: 10.1007/978-3-642-31284-7_19.  Google Scholar [42] O. S. Rothaus, On bent functions,, Journal of Combinatorial Theory, 20 (1976), 300.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar [43] V. M. Sidelnikov, On the mutual correlation of sequences,, Soviet Math. Dokl., 12 (1971), 531.   Google Scholar [44] Y. Tan, L. Qu, C. Tan and C. Li, New families of differentially 4-uniform permutations over $\mathbbF_{2^{2k}}$,, In T.Helleseth, 7280 (2012), 25.  doi: 10.1007/978-3-642-30615-0_3.  Google Scholar [45] G. Xu, X. Cao and S. Xu, Constructing new differentially 4-uniform permutations and APN functions over finite fields,, Cryptography and Communications - Discrete Structures, (2014).   Google Scholar [46] Y. Yu, M. Wang and Y. Li, Constructing low differential uniformity functions from known ones,, Chinese Journal of Electronics, 22 (2013), 495.   Google Scholar [47] Z. Zha, L. Hu and S. Sun, Constructing new differentially 4-uniform permutations from the Inverse function,, Finite Fields Applications, 25 (2014), 64.  doi: 10.1016/j.ffa.2013.08.003.  Google Scholar [48] Y. Zhou, $(2^n, 2^n, 2^n, 1)$-relative difference sets and their representations,, Journal of Combinatorial Designs, 21 (2013), 563.   Google Scholar

show all references

##### References:
 [1] C. M. Adams, Constructing symmetric ciphers using the CAST design procedure,, Designs, 12 (1997), 283.  doi: 10.1023/A:1008229029587.  Google Scholar [2] R. Anderson, E. Biham and L. Knudsen, Serpent: A proposal for the Advanced Encryption Standard,, National Institute of Standards and Technology AES Proposal, 174 (1998).   Google Scholar [3] T. Beth and C. Ding, On almost perfect nonlinear permutations,, Advances in Cryptology-EUROCRYPT'93, 765 (1993), 65.  doi: 10.1007/3-540-48285-7_7.  Google Scholar [4] E. Biham, R. Anderson and L. Knudsen, Serpent: A new block cipher proposal,, Fast Software Encryption, 1372 (1998), 222.  doi: 10.1007/3-540-69710-1_15.  Google Scholar [5] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems,, Journal of Cryptology, 4 (1991), 3.  doi: 10.1007/BF00630563.  Google Scholar [6] C. Blondeau and K. Nyberg, Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities,, EUROCRYPT 2014, 8441 (2014), 165.  doi: 10.1007/978-3-642-55220-5_10.  Google Scholar [7] M. Brinkmann and G. Leander, On the classification of APN functions up to dimension five,, Designs, 49 (2008), 273.  doi: 10.1007/s10623-008-9194-6.  Google Scholar [8] K. Browning, J. F. Dillon, M. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six,, Contemporary Mathematics, 518 (2010), 33.  doi: 10.1090/conm/518/10194.  Google Scholar [9] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin and C. Vikkelsoe, PRESENT: An Ultra-Lightweight Block Cipher,, CHES 2007, 4727 (2007), 450.  doi: 10.1007/978-3-540-74735-2_31.  Google Scholar [10] L. Budaghyan and C. Carlet, CCZ-equivalence of single and multi output Boolean functions,, AMS Contemporary Math., 518 (2010), 43.  doi: 10.1090/conm/518/10195.  Google Scholar [11] L. Budaghyan, C. Carlet and T. Helleseth, On bent functions associated to AB functions,, IEEE Information Theory Workshop, (2011), 150.  doi: 10.1109/ITW.2011.6089365.  Google Scholar [12] C. Bracken and G. Leander, A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree,, Finite Fields and Their Applications, 16 (2010), 231.  doi: 10.1016/j.ffa.2010.03.001.  Google Scholar [13] C. Bracken, C. H. Tan and Y. Tan, Binomial differentially 4-uniform permutations with high nonlinearity,, Finite Fields Applications, 18 (2012), 537.  doi: 10.1016/j.ffa.2011.11.006.  Google Scholar [14] C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems,, Designs, 15 (1998), 125.  doi: 10.1023/A:1008344232130.  Google Scholar [15] C. Carlet, Vectorial boolean functions for cryptography,, Chapter of the monography Boolean Models and Methods in Mathematics, (2010), 398.  doi: 10.1017/CBO9780511780448.012.  Google Scholar [16] C. Carlet, On known and new differentially 4-uniform functions,, Proceedings of the 16th Australisian Conference on Information Security and Privacy (ACISP) 2011, 6812 (2011), 1.  doi: 10.1007/978-3-642-22497-3_1.  Google Scholar [17] L. Carlitz, Explicit evaluation of certain exponential sums,, In Math. Scand., 44 (1979), 5.   Google Scholar [18] P. Charpin, T. Helleseth and V. A. Zinoviev, The divisibility modulo 24 of Kloosterman sums on $GF(2^m)$, $m$ odd,, Journal of Combinatorial Theory, 114 (2007), 322.  doi: 10.1016/j.jcta.2006.06.002.  Google Scholar [19] F. Chabaud and S. Vaudenay, Links between differential and linear cryptanalysis,, EUROCRYPT'94, 950 (1995), 356.  doi: 10.1007/BFb0053450.  Google Scholar [20] J. Daemen and V. Rijmen, The Design of Rijndael: AES: The Advanced Encryption Standard,, Springer, (2002).  doi: 10.1007/978-3-662-04722-4.  Google Scholar [21] J. F. Dillon, Elementary Hadamard Difference Sets,, Ph.D. Dissertation. University of Maryland, (1974).   Google Scholar [22] H. Dobbertin, Almost perfect nonlinear power functions over GF($2^n$): The Niho case,, Information and Computation, 151 (1999), 57.  doi: 10.1006/inco.1998.2764.  Google Scholar [23] H. Dobbertin, Almost perfect nonlinear power functions over GF($2^n$): The Welch case,, IEEE Transactions on Information Theory, 45 (1999), 1271.  doi: 10.1109/18.761283.  Google Scholar [24] H. Dobbertin, Almost perfect nonlinear power functions on $GF(2^n)$: a new case for $n$ divisible by 5,, Proceedings of Finite Fields and Applications Fq5, (2001), 113.   Google Scholar [25] European Telecommunications Standards Institute, Technical Specification 135 202 V9.0.0: Universal mobile telecommunications system (UMTS); LTE;, specification of the 3GPP confidentiality and integrity algorithms; Document 2: KASUMI specification (3GPP TS 35.202 V9.0.0 Release 9)., ().   Google Scholar [26] R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions,, IEEE Transactions on Information Theory, 14 (1968), 154.  doi: 10.1109/TIT.1968.1054106.  Google Scholar [27] S. Hu, S. Li, T. Zhang, T. Feng and G. Ge, New pseudo-planar binomials in characteristic two and related schemes,, Designs, 76 (2015), 345.  doi: 10.1007/s10623-014-9958-0.  Google Scholar [28] T. Kasami, The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes,, Information and Control, 18 (1971), 369.  doi: 10.1016/S0019-9958(71)90473-6.  Google Scholar [29] L. R. Knudsen and M. Robshaw, The Block Cipher Companion,, Springer, (2011).  doi: 10.1007/978-3-642-17342-4.  Google Scholar [30] L. R. Knudsen, Truncated and higher order differentials,, Proceedings of Fast Software Encryption, 1008 (2005), 196.  doi: 10.1007/3-540-60590-8_16.  Google Scholar [31] G. Lachaud and J. Wolfmann, The weights of the orthogonals of the extended quadratic binary Goppa codes,, IEEE Transactions on Information Theory, 36 (1990), 686.  doi: 10.1109/18.54892.  Google Scholar [32] G. Leander and A. Poschmann, On the classification of 4 Bit S-boxes,, WAIFI 2007. Lecture Notes in Computer Science, 4547 (2007), 159.  doi: 10.1007/978-3-540-73074-3_13.  Google Scholar [33] M. Matsui, Block encryption algorithm MISTY,, Fast Software Encryption, 1267 (1997), 54.  doi: 10.1007/BFb0052334.  Google Scholar [34] M. Matsui, Linear cryptanalysis method for DES cipher,, Advances in Cryptology - EUROCRYPT'93, 765 (2001), 386.  doi: 10.1007/3-540-48285-7_33.  Google Scholar [35] 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).   Google Scholar [36] 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), 49.   Google Scholar [37] K. Nyberg, Perfect nonlinear S-boxes,, Advances in Cryptology, 547 (1991), 378.  doi: 10.1007/3-540-46416-6_32.  Google Scholar [38] K. Nyberg, S-boxes and round functions with controllable linearity and differential uniformity,, Fast Software Encryption (FSE'94), 1008 (1995), 111.  doi: 10.1007/3-540-60590-8_9.  Google Scholar [39] K. Nyberg and L. R. Knudsen, Provable security against differential cryptanalysis,, Proceedings of CRYPT0'92, 740 (1993), 566.  doi: 10.1007/3-540-48071-4_41.  Google Scholar [40] K. Nyberg and L. R. Knudsen, Provable security against a differential attack,, Journal of Cryptology, 8 (1995), 27.  doi: 10.1007/BF00204800.  Google Scholar [41] G. Piret, T. Roche and C. Carlet, PICARO - A block cipher allowing efficient higher-order side-channel resistance,, Proceedings of 10th International Conference in Applied Cryptography and Network Security 2012, 7341 (2012), 311.  doi: 10.1007/978-3-642-31284-7_19.  Google Scholar [42] O. S. Rothaus, On bent functions,, Journal of Combinatorial Theory, 20 (1976), 300.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar [43] V. M. Sidelnikov, On the mutual correlation of sequences,, Soviet Math. Dokl., 12 (1971), 531.   Google Scholar [44] Y. Tan, L. Qu, C. Tan and C. Li, New families of differentially 4-uniform permutations over $\mathbbF_{2^{2k}}$,, In T.Helleseth, 7280 (2012), 25.  doi: 10.1007/978-3-642-30615-0_3.  Google Scholar [45] G. Xu, X. Cao and S. Xu, Constructing new differentially 4-uniform permutations and APN functions over finite fields,, Cryptography and Communications - Discrete Structures, (2014).   Google Scholar [46] Y. Yu, M. Wang and Y. Li, Constructing low differential uniformity functions from known ones,, Chinese Journal of Electronics, 22 (2013), 495.   Google Scholar [47] Z. Zha, L. Hu and S. Sun, Constructing new differentially 4-uniform permutations from the Inverse function,, Finite Fields Applications, 25 (2014), 64.  doi: 10.1016/j.ffa.2013.08.003.  Google Scholar [48] Y. Zhou, $(2^n, 2^n, 2^n, 1)$-relative difference sets and their representations,, Journal of Combinatorial Designs, 21 (2013), 563.   Google Scholar

2019 Impact Factor: 0.734