Paper 2018/1046

Constructing Infinite Families of Low Differential Uniformity $(n,m)$-Functions with $m>n/2$

Claude Carlet, Xi Chen, and Longjiang Qu


Little theoretical work has been done on $(n,m)$-functions when $\frac {n}{2}<m<n$, even though these functions can be used in Feistel ciphers, and actually play an important role in several block ciphers. Nyberg has shown that the differential uniformity of such functions is bounded below by $2^{n-m}+2$ if $n$ is odd or if $m>\frac {n}{2}$. In this paper, we first characterize the differential uniformity of those $(n,m)$-functions of the form $F(x,z)=\phi(z)I(x)$, where $I(x)$ is the $(m,m)$-Inverse function and $\phi(z)$ is an $(n-m,m)$-function. Using this characterization, we construct an infinite family of differentially $\Delta$-uniform $(2m-1,m)$-functions with $m\geq 3$ achieving Nyberg's bound with equality, which also have high nonlinearity and not too low algebraic degree. We then discuss an infinite family of differentially $4$-uniform $(m+1,m)$-functions in this form, which leads to many differentially $4$-uniform permutations. We also present a method to construct infinite families of $(m+k,m)$-functions with low differential uniformity and construct an infinite family of $(2m-2,m)$-functions with $\Delta\leq2^{m-1}-2^{m-6}+2$ for any $m\geq 8$. The constructed functions in this paper may provide more choices for the design of Feistel ciphers.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Designs, Codes and Cryptography
APN functionDifferential UniformityNyberg's boundSubstitution boxesSemi-bent function
Contact author(s)
1138470214 @ qq com
2018-11-02: received
Short URL
Creative Commons Attribution


      author = {Claude Carlet and Xi Chen and Longjiang Qu},
      title = {Constructing Infinite Families of Low Differential Uniformity $(n,m)$-Functions with $m>n/2$},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1046},
      year = {2018},
      doi = {10.1007/s10623-018-0553-7},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.