Shift-invariant permutations with clear algebraic structure for cryptography
A Class of Shift-Invariant Permutations and Their Algebraic Structure
Information Theory
Summary
Shift-invariant permutations are special ways of rearranging data bits that repeat in a regular pattern, making them efficient to use in encryption. The authors study a particular family of these permutations based on mathematical objects called landscapes and find when their building blocks combine nicely like polynomials. They show how these permutations can be understood using polynomial math, making it easier to find when they have good cryptographic properties and to compute their reverses and repeated applications. Their work includes explicit formulas, criteria, and many examples that unify previous known constructions.
What this means in practice
- •For symmetric cryptography engineers: Build efficient and regular permutations for cryptographic algorithms using polynomial-based criteria and explicit formulas to ensure invertibility and security properties.
- •For hardware designers: Design hardware implementations of shift-invariant permutations with predictable algebraic structure that simplify computation and reduce resource usage in encryption modules.
A theory result. No direct application yet.
Authors
Cheng Lyu, Dabin Zheng, Mu Yuan, Lei Hu
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 $\{γ_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 $\{γ_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 $\{γ_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.