Theoretical Foundations of Applied Discrete Mathematics

Classes of permutations of Abelian groups with high nonlinearity and low differential $\delta$-uniformity

D. A. Burov, D. A. Kononov


Abstract: This paper is devoted to the construction and study of the differential $\delta$-uniformity $\delta(f)$ and the nonlinearity $\mathcal{NL}(f)$ of permutations over Abelian groups. Let $p$ be a prime number, $q = p^n$, $n \in \mathbb{N}$, and let $\mathbb{F}_q$ be the finite field of $q$ elements. Let $\mathbb{F}_q^{\ast}$ be the multiplicative group of $\mathbb{F}_q$. The deficiency $D(f)$ of a mapping $f$ of Abelian groups is defined as the number of zeros in its difference distribution table. It has been proved that $\mathcal{NL}(f) \geq 1 - \dfrac{1}{n}\sqrt{2 + 2D(f)}$ for any bijective mapping $f$ of Abelian groups of order $n$. For the logarithmic permutation $f \in S(\mathbb{F}_q^{\ast})$, the lower bound $\mathcal{NL}(f) \geq \dfrac{q - \sqrt{q} - 2}{q - 1}$ has been proved. Using the mapping $(x, y) \mapsto x + y$ for $x, y \in \mathbb{F}_q$, differentially $5$-uniform permutations over the group $\mathbb{F}_{17}^{\ast} \times \mathbb{F}_{17}^{\ast}$ have been constructed. Classes of differentially $3$-uniform permutations over $\mathbb{F}_q^{\ast}$ have been obtained by modifying logarithmic permutations on $\mathbb{F}_q^{\ast}$. For such permutations, the bound $\mathcal{NL}(f) \geq 1 - \dfrac{\sqrt{q^m} + 2q - 1}{q^m - 1}$ is true. By augmenting the logarithmic permutation over $\mathbb{Z}_{q-1}$ with a Boolean function, classes of differentially 6-uniform and differentially 5-uniform permutations on the additive group of the ring $\mathbb{Z}_2 \times \mathbb{Z}_{q-1}$ have been constructed. It is proven that for permutations of the group $\mathbb{F}_{2^n}^{\ast}$ defined by the polynomial $x^4 + a x^2 + b x$, the differential uniformity satisfies $\delta(f) \leq 3$, and the nonlinearity satisfies $\mathcal{NL}(f) \geq 1 - \dfrac{3\sqrt{2^n}}{2^n - 1}$.

Keywords: permutation of finite field, $s$-box, nonlinearity, differential $\delta$-uniformity, logarithmic permutation.

UDC: 519.7

DOI: 10.17223/2226308X/18/1