There are siblings of $\chi$ which are permutations for $n$ even

Abstract

Let $1$ be the all-one vector and $\odot$ denote the component-wise multiplication of two vectors in ${\mathbb{F}}_2^n$. We study the vector space ${\Gamma }_n$ over ${\mathbb{F}}_2$ generated by the functions ${\gamma }_{2k}:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n,k\ge 0$, where $${\gamma }_{2k}=S^{2k}\odot (1+S^{2k-1})\odot (1+S^{2k-3})\odot \dots \odot (1+S)$$ and $S:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^n$ is the cyclic left shift function. The functions in ${\Gamma }_n$ are shift-invariant and the well known $\chi$ function used in several cryptographic primitives is contained in ${\Gamma }_n$. For even $n$, we show that the permutations from ${\Gamma }_n$ with respect to composition form an Abelian group, which is isomorphic to the unit group of the residue ring ${\mathbb{F}}_2[X]/(X^n+X^{n/2})$. This isomorphism yields an efficient theoretic and algorithmic method for constructing and studying a rich family of shift-invariant permutations on ${\mathbb{F}}_2^n$ which are natural generalizations of $\chi$. To demonstrate it, we apply the obtained results to investigate the function ${\gamma }_0+{\gamma }_2+{\gamma }_4$ on ${\mathbb{F}}_2^n$.