Cryptology ePrint Archive: Report 2018/1046

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

Claude Carlet and Xi Chen* and Longjiang Qu

Abstract: 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.

Category / Keywords: secret-key cryptography / APN function, Differential Uniformity, Nyberg's bound, Substitution boxes, Semi-bent function

Original Publication (with minor differences): Designs, Codes and Cryptography

Date: received 29 Oct 2018

Contact author: 1138470214 at qq com

Available format(s): PDF | BibTeX Citation

Version: 20181102:010140 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]