The locally crooked permutations and the complete permutations over F2n

Abstract The crooked function has a fixed point $0$ and all its difference set is the complement of the hyperplane. In this paper, we proposed the locally crooked permutation, at least one of its differential sets is the complement of a hyperplane. We found a close relationship between the locally crooked permutation and the complete permutation. Specifically, the complete permutations over $\mathbb{F}_{2^{n}}$ can be obtained from the locally crooked permutations over $\mathbb{F}_{2^{n+1}}$, and vice versa. In particular, we construct the complete permutations with best-known differential uniformity and nonlinearity and the locally crooked permutations with differential uniformity of $4$ over $\mathbb{F}_{2^{2n}}$. Besides, we also found that the existence of the APN permutation that is locally crooked over $\mathbb{F}_{2^{2n+2}}$ is closely related to the nonlinear complete permutation over $\mathbb{F}_{2^{2n+1}}$. MSC Classification: 05A05 , 11T06 , 11T55