Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure
Abstract
Shift-invariant permutations of 𝔽2n are particularly 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 𝔽2n constructed from a recursively defined sequence of mappings {γj}j≥ 0 associated with landscapes. First, we prove that, under an explicit dimension condition relating n to the support of the landscape, the sequence {γj}j≥ 0 has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on 𝔽2n with a nonzero special index. Then, we determine the eventual zero or periodic behavior of {γj}j≥0, including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. 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 𝔽2[z]/⟨ p(z)⟩, where p(z) is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.
Related
- Construction of New Complete Complementary Codes Using Extended Boolean Functions and Permutations
- Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
- Invariant Measures on Smooth Algebraic Groups over Higher Local Fields
- A polynomial invariant of planar curves
- Algebraic Structure and Orthogonality Properties of Rational Polynomial Phase Rings on Discrete Lattices
BibTeX
@misc{lyu2026shiftinvariant,
title = {{Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure}},
author = {Cheng Lyu and Dabin Zheng and Mu Yuan and Lei Hu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.31174},
eprint = {2609.31174},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31174},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure
AU - Cheng Lyu
AU - Dabin Zheng
AU - Mu Yuan
AU - Lei Hu
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2609.31174
UR - https://arxiv.org/abs/2609.31174
AB - Shift-invariant permutations of 𝔽_2^n are particularly 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 𝔽_2^n constructed from a recursively defined sequence of mappings {γ_j}_j≥ 0 associated with landscapes. First, we prove that, under an explicit dimension condition relating n to the support of the landscape, the sequence {γ_j}_j≥ 0 has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on 𝔽_2^n with a nonzero special index. Then, we determine the eventual zero or periodic behavior of {γ_j}_j≥0, including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. 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 𝔽_2[z]/⟨ p(z)⟩, where p(z) is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.
ER -