Constructions of complete permutations over ${\mathbb{F}}_q^n$

Abstract

Complete permutation polynomials play an important role in cryptography, particularly in the design of cryptographic primitives such as the Lai--Massey scheme and S-boxes. We generalize a result of Sun, Li, Guo, and Qu (2021) by characterizing the complete permutation behavior of the mapping $\Psi (X)=M(X+\psi (AX))$ over ${\mathbb{F}}_q^n$, where ${\mathbb{F}}_q$ is a finite field of $q$ elements with $q$ being a prime power, $M\in GL(n,{\mathbb{F}}_q)$, $GL(n,{\mathbb{F}}_q)$ is the general linear group of order $n$ over ${\mathbb{F}}_q$, $A_{m\times n}$ is a full-rank matrix over ${\mathbb{F}}_q$, and $\psi =({\psi }_1,{\psi }_2,\dots ,{\psi }_n)$ with each component function ${\psi }_i:{\mathbb{F}}_q^m\to {\mathbb{F}}_q$. Furthermore, we establish criteria for the permutation and complete permutation properties of the mapping $F(X)=T(X+B^{t}f(AX))$ over ${\mathbb{F}}_q^n$, $f:{\mathbb{F}}_q^m\to {\mathbb{F}}_q^{n-m}$, $T\in GL(n,{\mathbb{F}}_q)$, $A_{m\times n}$ and $B_{(n-m)\times n}$ are full-rank matrices over ${\mathbb{F}}_q$, $B^t$ represents the transpose of the matrix $B$, and $0<m<n$ are integers. These results also generalize an earlier result of Gravel and Panario (2023), who showed that any arbitrary function $f$ from ${\mathbb{F}}_q^m$ to ${\mathbb{F}}_q^{n-m}$ can be extended to a bijection over ${\mathbb{F}}_q^n$ through the mapping $F(X)=T(X+B^{t}f(AX))$, under the condition $A{B}^t=0$. Here we do not impose the restriction that $A{B}^t=0$.