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

arXiv:2203.00778 · math.CO, cs.CR, cs.IT, math.IT · Submitted 2022-03-01 · Read on arXiv

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