Affine and cyclic affine equivalence of rotation-symmetric S-boxes
math.CO, cs.CR, cs.IT, math.IT
Submitted: 2022-03-01
Updated: 2026-11-01
Comments: 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
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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 χ used in Keccak is a well-known example. Ordinary affine equivalence allows arbitrary invertible affine transformations, which need not preserve rotation symmetry. We introduce cyclic affine equivalence, in which the implementing transformations each have an invertible k-circulant linear part with (k,n)=1 and a translation vector fixed by the shift. For n at least3, 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 at least3, explicit constructions exhibit affine classes containing several cyclic affine classes. We derive exact class-size formulas, count cyclic affine classes for 3 at most n at most9, 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.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality