Affine and cyclic affine equivalence of rotation-symmetric S-boxes

Abstract

A rotation-symmetric S-box on $n$ bits is a vectorial Boolean function that commutes with the right cyclic shift and is therefore determined by a single Boolean function. The map $\chi$ used in Keccak is a well-known example. Ordinary affine equivalence allows arbitrary invertible affine transformations, which need not preserve rotation symmetry. We introduce \emph{cyclic affine equivalence}, in which the implementing transformations each have an invertible $k$-circulant linear part with $\gcd (k,n)=1$ and a translation vector fixed by the shift. For $n\ge 3$, the two relations give the same classes of rotation-symmetric permutations exactly when $n$ is an odd prime for which $2$ is a primitive root. In every other dimension $n\ge 3$, explicit constructions exhibit affine classes containing several cyclic affine classes. We derive exact class-size formulas, count cyclic affine classes for $3\le n\le 9$, and classify a four-bit family of $\chi$-siblings under both relations. Finally, we characterize when a permutation is affinely equivalent to a rotation-symmetric one and apply the criterion to the Ascon S-box.

arXiv comment30 pages; new title and substantial revision, including a dimension classification for affine versus cyclic affine equivalence, new counting results, and corrected lifting theory and tables