Unicyclic Strong Permutations
Preprint
Abstract
In this paper, we study some properties of a certain kind of permutation $\sigma$ over $\mathbb{F}_{2}^{n}$, where $n$ is a positive integer. The desired properties for $\sigma$ 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 $2^{n-1}$. We call permutations that satisfy these three properties simultaneously unicyclic strong permutations. We prove that our permutations $\sigma$ always have high algebraic degree and that the average number of terms of each component function tends to $2^{n-1}$. We also give a condition on the cycle structure of $\sigma$. We observe empirically that for $n$ even, our construction does not provide unicylic permutations. For $n$ odd, $n \leq 11$, we conduct an exhaustive search of all $\sigma$ 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 $\sigma$.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Handbook of Finite Fields2013
- Average Case Analysis of Algorithms on Sequences2001
- Differential cryptanalysis of DES-like cryptosystemsJournal of Cryptology, 1991
- The generation of random permutations on the flyInformation Processing Letters, 1988
- Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)IEEE Transactions on Information Theory, 1984