New Constructions of Complete Permutations
Bing Sun, Kangquan Li, Jian Guo, Longjiang Qu · IEEE Transactions on Information Theory · 2021
In this paper, we aim to construct a class of complete permutations$\mathcal F$over$\mathbb F_{q}^{n}$from some polynomials$f_{1},f_{2},\ldots,f_{n}$over$\mathbb F_{q}$. First of all, we determine a necessary and sufficient condition such that$\mathcal F$is complete. Briefly, we transform the completeness of$\mathcal F$into showing the permutation properties of two polynomials over$\mathbb F_{q}$obtained from these$f_{i}$’s. Then, following the wide applications, we investigate the constructions of linear complete permutations over$\mathbb F_{2}^{n}$based on the rotations andXORs. The following two cases are considered: the first one is to use some different circularly left shift transforms$f_{i}$’s and the second one is to assume$f_{i}$’s are of the form$b_{i}f$with a fixed$f$and different$b_{i}$’s in$\mathbb F_{q}$. In both cases, we show that the completeness of the permutation is closely related to the ranks of some matrices with particular forms, which can be determined by the cycle decomposition of the permutation over the$n$branches. Besides, we present several explicit linear complete permutations which might be used in the design as well as the provable security of cryptographic schemes.