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 σ.

Algebraic degree, Boolean functions, Differential uniformity, Finite fields, Permutations, Walsh spectra
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