Advances in Mathematics of Communications (AMC)

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

Pages: 541 - 565, Volume 9, Issue 4, November 2015      doi:10.3934/amc.2015.9.541

       Abstract        References        Full Text (516.8K)       Related Articles       

Claude Carlet - Department of Mathematics, LAGA, University of Paris 8, (and LAGA, University of Paris 13, CNRS), France (email)
Yousuf Alsalami - Department of Computer Engineering, Khalifa University of Science, Technology and Research, United Arab Emirates (email)

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

Keywords:  Block ciphers, S-boxes, vectorial Boolean functions, APN functions, di erentially 4-uniform functions.
Mathematics Subject Classification:  Primary: 11T71, 94A60; Secondary: 68P25.

Received: May 2014;      Revised: January 2015;      Available Online: November 2015.