Paper 2026/1249

A family of invertible shift-invariant maps with strong arithmetic properties

Abstract

Shift-invariant maps have been employed to design nonlinear layers in many symmetric cryptographic schemes, such as the $\chi$-map used in Keccak. In this paper, we study a family of shift-invariant maps on $\mathbb{F}_2^n$ which exhibit strong arithmetic properties with respect to the composition. The set of their defining functions, which we denote by $\Omega_{\underline{a}}$, is induced by a so-called ``bifix-free'' sequence $\underline{a}=(a_1,a_2,\ldots,a_m)\in \mathbb{F}_2^m$ with $2\leq m<n$. It is shown that $\Omega_{\underline{a}}$ forms a commutative monoid with respect to the composition. If $m\nmid n$, then $\Omega_{\underline{a}}$ is isomorphic to the unit group of $\mathbb{F}_2[x]/ (x^{\lceil \frac{n}{m} \rceil})$; if $m\mid n$, then the unit group of $\Omega_{\underline{a}}$ is isomorphic to that of $\mathbb{F}_2[x]/ (x^{ \frac{2n}{m}}+x^{ \frac{n}{m}})$. The isomorphic relation transforms the composition of functions in $\Omega_{\underline{a}}$ into the multiplication of polynomials in the quotient ring of $\mathbb{F}_2[x]$, where the algebraic properties of the latter are well-understood. As a straightforward application, we focus on the algebraic properties of a particular class of functions in $\Omega_{\underline{a}}$, denoted by $\rho_k$ for $k\geq 1$, which include the $\chi$-map as well as several other known maps studied in earlier literature. It is shown that $\rho_k$ is invertible if and only if $m\nmid n$. Also the inverse and the cycle structure of $\rho_k$ (if invertible) can be fully characterized. As different bifix-free sequences $\underline{a}$ typically induce different families of functions $\Omega_{\underline{a}}$ with pairwise trivial intersections, this work offers abundant parameter flexibility for designing invertible shift-invariant maps as well as deep insights into their algebraic properties.