arXiv:2203.00778 · v3
Affine and cyclic affine equivalence of rotation-symmetric S-boxes
摘要
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 $χ$ 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\ge3$, 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\ge3$, explicit constructions exhibit affine classes containing several cyclic affine classes. We derive exact class-size formulas, count cyclic affine classes for $3\le n\le9$, and classify a four-bit family of $χ$-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.
作者备注：30 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