A Class of Shift-Invariant Permutations and Their Algebraic Structure

Abstract

Shift-invariant permutations of $\mathbb F_2^n$ are attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of $\mathbb F_2^n$ generated by a recursively defined sequence of mappings $\{\gamma_j\}_{j\ge0}$ associated with landscapes. First, we prove that, under an explicit dimension condition on $n$ and the support of the landscape, the sequence $\{\gamma_j\}_{j\ge0}$ has the polynomial composition property if and only if the corresponding landscape with nonzero special index is quasi-conserved on $\mathbb F_2^n$. Then, we determine the eventual zero or periodic behavior of $\{\gamma_j\}_{j\ge0}$, including the first zero or periodic index and the least eventual period, and establish linear independence up to the first relation. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring $\mathbb F_2[z]/\langle p(z)\rangle$, where $p(z)$ is a monomial or a binomial determined by the landscape. This framework reduces the permutation property, compositional inverse, order, and iterates of these mappings to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas. We tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.