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

Additional Metadata
Keywords Algebraic degree, Boolean functions, Differential uniformity, Finite fields, Permutations, Walsh spectra
Persistent URL dx.doi.org/10.1007/s12095-019-00384-4
Journal Cryptography and Communications
Citation
Gravel, C. (Claude), Panario, D, & Thomson, D. (David). (2019). Unicyclic strong permutations. Cryptography and Communications. doi:10.1007/s12095-019-00384-4