In this paper, we study some properties of a certain kind of permutation σ over F2n, where n is a positive integer. The desired properties for σ are: (1) the algebraic degree of each component function is n − 1; (2) the permutation is unicyclic; (3) the number of terms of the algebraic normal form of each component is at least 2n− 1. We call permutations that satisfy these three properties simultaneously unicyclic strong permutations. We prove that our permutations σ always have high algebraic degree and that the average number of terms of each component function tends to 2n− 1. We also give a condition on the cycle structure of σ. We observe empirically that for n even, our construction does not provide unicylic permutations. For n odd, n ≤ 11, we conduct an exhaustive search of all σ given our construction for specific examples of unicylic strong permutations. We also present some empirical results on the difference tables and linear approximation tables of σ.

, , , , ,
Cryptography and Communications
School of Mathematics and Statistics

Gravel, C. (Claude), Panario, D, & Thomson, D. (David). (2019). Unicyclic strong permutations. Cryptography and Communications. doi:10.1007/s12095-019-00384-4