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 F_2ⁿ can be obtained from the locally crooked permutations over F_2ⁿ⁺¹, 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 F_2²ⁿ. Besides, we also found that the existence of the APN permutation that is locally crooked over F_2²ⁿ⁺² is closely related to the nonlinear complete permutation over F_2²ⁿ⁺¹. MSC Classification: 05A05 , 11T06 , 11T55