Linear Self-Symmetries of Inverse-Based S-boxes: Generic Rigidity and Applications

Linear Self-Symmetries of Inverse-Based S-boxes: Generic Rigidity and Applications

arXiv:2610.29837v1 [cs.CR] 21 Oct 2026

Zheng Zhang ∗Na Zhang †

Abstract Finite-field inversion is a basic nonlinear building block in the design of S-boxes for symmetric cryptography. In inverse-based S-boxes, finite-field inversion is often combined with linear or affine layers that may preserve or destroy algebraic symmetries of the inverse function. We study how often nontrivial linear self-symmetries remain as the outer invertible linear transformation varies over GLn (F2 ). Using the classification of two-sided linear equivalences of inversion, we reduce the problem to semilinear conjugacy and centralizer estimates. We obtain matching upper and lower bounds for the probability that a nontrivial linear self-symmetry remains, and these bounds determine its leading quadratic exponent. This exponent is governed by the smallest prime divisor of the extension degree. Thus the decay rate depends on the arithmetic of the field extension and not only on its dimension. As cryptographic applications, we provide a practical rigidity criterion, prove that the full AES S-box has no nontrivial linear self-symmetry, and illustrate the broader relevance of the framework through ARIA and Vision.

Keywords: finite-field inversion, linear stabilizers, semilinear conjugacy, centralizers, inverse-based Sboxes.

1

Introduction

Finite-field inversion on F2n is one of the best-known nonlinear maps used in the design of S-boxes for symmetric-key cryptography. Its algebraic structure is also highly symmetric. If J(x) = x−1 ,

J(0) = 0, r

then J commutes with every Frobenius automorphism x 7→ x2 . Thus inversion comes with a natural family of nontrivial linear symmetries. In inverse-based S-box constructions, inversion is usually combined with an outer linear or affine layer, and such a layer may preserve or destroy symmetries of the inverse function. This raises a natural structural question: when the outer linear layer varies, how often does any nontrivial symmetry of inversion survive? To make the question precise, for a map Φ : F2n → F2n , define Stab(Φ) = {T ∈ GLn (F2 ) : T ◦ Φ = Φ ◦ T }. A nonidentity element of Stab(Φ) is a nontrivial linear self-symmetry of Φ, and we call Φ rigid when Stab(Φ) = {I}. Remark 1. We emphasize that this notion is different from linear self-equivalence. A linear self-equivalence allows a pair of linear maps acting separately on the input and output, whereas a linear self-symmetry in the sense above requires the same linear map to commute with Φ. ∗ Corresponding author. Department of Mathematics, Towson University, 7800 York Rd, Towson, MD 21204, USA. Email: zhengzhang@towson.edu. † Department of Mathematics, Towson University, 7800 York Rd, Towson, MD 21204, USA. Email: nzhang@towson.edu.

1

We study the family ΦA = A ◦ J,

A ∈ GLn (F2 ),

and measure the frequency with which ΦA retains a nontrivial linear self-symmetry. Self-symmetries are especially natural in iterative constructions. When the same linear transformation is compatible with the S-box, the diffusion layer, and the round constants, it can propagate from one round to the next without changing form. Such self-symmetries therefore represent algebraic structure that can persist through repeated applications of the round function and may give rise to invariant state spaces or other non-random structure [11]. Understanding when such self-symmetries survive is therefore relevant to both the design and the structural analysis of inverse-based S-boxes. This setting arises naturally in several inverse-based cryptographic constructions. The AES S-box is the best-known example, where inversion over F28 is followed by a fixed affine layer [15]. Related inverse-based substitution layers also appear in ARIA [12], while more recent designs such as Vision use inversion together with sparse linearized polynomials over binary fields [1]. These examples show that the interaction between finite-field inversion and surrounding linear structure is a recurring feature of inverse-based cryptographic design. This problem is related to several lines of work on symmetry, equivalence, and self-equivalence of cryptographic functions. Rijmen, Barreto, and Gazzoni Filho [18] studied rotation symmetry in S-boxes generated algebraically from finite-field power maps. Related work has further examined rotation-symmetric S-boxes and their affine-equivalence classes [9, 16]. Algebraic and alternative representations of Rijndael have also been studied extensively [19, 13, 2]. These works show that finite-field structure and surrounding linear transformations can produce useful symmetries and alternative representations of S-boxes, but they address a different question from the survival problem considered here. More generally, linear, affine, EA, and CCZ equivalence provide standard frameworks for comparing vectorial Boolean functions [5, 3, 4, 6]. Self-equivalences have also been studied in white-box cryptography [17]. For inversion specifically, Kölsch [10] obtained strong classifications of its CCZ and EA equivalence classes. These notions allow broader input and output transformations than the commuting linear selfsymmetries considered here. More directly related to our problem, Yuan et al. [20] classified the two-sided linear equivalences J ◦ T = U ◦ J. Their classification identifies the possible transformations that can occur in the stabilizer of A◦J. Ishizuka [8] recently proved generic stabilizer triviality in the full space of vectorial functions. In contrast, we consider the structured family {A ◦ J : A ∈ GLn (F2 )}. The above works do not determine how frequently a nontrivial linear self-symmetry survives in this family, or how that frequency depends on the arithmetic of n. Let En = {A ∈ GLn (F2 ) : Stab(A ◦ J) ̸= {I}} and pn =

|En | . |GLn (F2 )|

Thus pn is the probability that a uniformly chosen outer linear transformation leaves a nontrivial linear self-symmetry of the transformed inversion map. Our main result determines the exact leading quadratic exponent of pn . Main Theorem. Let q(n) be the smallest prime divisor of n, and let Y κ= (1 − 2−j ). j≥1

For n ≥ 4, 2

κq(n) 2−n (1−1/q(n)) ≤ pn ≤ 2

n −n2 (1−1/q(n))+n 2 . κ

Consequently,  − log2 pn = n2 1 −

1 q(n)

 + O(n).

In particular, when n is even the leading quadratic term is n2 /2, while for prime n it is n2 . Thus the rate at which nontrivial self-symmetries disappear depends strongly on the arithmetic of the extension degree. The theorem can be read in two ways. For designers who want symmetry, En measures the set of outer linear layers that preserve a nontrivial self-symmetry of inversion. For designers who want to avoid symmetry, the theorem shows that a generic outer layer removes all such symmetries. Common S-box dimensions such as n = 4 and n = 8 lie in the least favorable case q(n) = 2, which motivates direct checks for concrete constructions. We develop several cryptographic applications in Section 5. We provide a simple rigidity criterion and apply it to the AES S-box, use ARIA to illustrate the propagation of byte-wise self-symmetries through binary diffusion, and consider Vision as a large-field example. We also briefly discuss Camellia [14] and SM4 [7] as related inverse-based constructions. The paper is organized as follows. Section 2 introduces the notation and the basic symmetry structure of finite-field inversion. Section 3 develops the structural estimates for the exceptional set. Section 4 proves the main theorem. Section 5 develops cryptographic applications to inverse-based S-boxes, including AES, ARIA, and Vision. Section 6 concludes the paper.

2

Notation and Inversion Symmetries

In this section, we fix the notation and recall the basic structural facts about finite-field inversion and its linear symmetries that will be used throughout the paper. Let J denote the inverse function on F2n , extended by J(0) = 0. For A ∈ GLn (F2 ), we write ΦA = A ◦ J. This family is natural in the study of inversion-based S-boxes, where an outer linear layer may preserve or destroy linear self-symmetries of inversion. Definition 2. For a map Φ : F2n → F2n , its linear stabilizer is Stab(Φ) = {T ∈ GLn (F2 ) : T ◦ Φ = Φ ◦ T }. For the family ΦA = A ◦ J, define the set En = {A ∈ GLn (F2 ) : Stab(ΦA ) ̸= {I}} , and let pn =

|En | . |GLn (F2 )|

A nonidentity element of Stab(Φ) represents a nontrivial linear self-symmetry of Φ. Thus, triviality of the stabilizer means that no nontrivial linear change of coordinates preserves the map. In particular, pn is the probability that a uniformly chosen outer linear transformation A leaves a nontrivial linear self-symmetry in ΦA = A ◦ J. The central question is therefore which linear self-symmetries of the inverse function can survive after composition with an outer linear transformation. To address this question, we study the symmetries of J, which arise from the Frobenius action on F2n . Let σ(x) = x2 denote the Frobenius automorphism of F2n . Since inversion commutes with Frobenius, J ◦ σ = σ ◦ J, and hence ⟨σ⟩ ⊆ Stab(J). Thus, the symmetry problem for ΦA begins with the interaction between the outer linear map A and the Frobenius symmetries inherent in J. To make this interaction precise, we use the classification of two-sided linear equivalences of the inverse function due to Yuan et al [20]. For a ∈ F× 2n and 0 ≤ r < n, let Ma (x) = ax,

Ta,r = Ma ◦ σ r ,

Ua,r = Ma−1 ◦ σ r .

These are semilinear maps obtained by combining field multiplication with a Frobenius power. The following theorem gives the complete list of two-sided linear equivalences of J stated in the notation used here. 3

Theorem 3 (Yuan et al. [20]). Let n ≥ 4 and let T, U ∈ GLn (F2 ). Then J ◦T =U ◦J if and only if there exist a ∈ F× 2n and 0 ≤ r < n such that U = Ma−1 ◦ σ r .

T = Ma ◦ σ r ,

The relevance of Theorem 3 to our setting is immediate. If T ∈ Stab(ΦA ), then T ◦ A ◦ J = A ◦ J ◦ T, or equivalently, J ◦ T = (A−1 T A) ◦ J. Thus Theorem 3 shows that every linear self-symmetry of ΦA must arise from one of the semilinear pairs Ua,r = Ma−1 ◦ σ r ,

Ta,r = Ma ◦ σ r , with

A−1 Ta,r A = Ua,r . Consequently, the problem of determining whether ΦA has a nontrivial linear stabilizer is reduced to a conjugacy problem between these semilinear maps. To encode this condition, for T, U ∈ GLn (F2 ), let C(T, U ) = {A ∈ GLn (F2 ) : A−1 T A = U }. Thus C(T, U ) consists precisely of the outer linear transformations that conjugate T to U . The reduction above can now be stated explicitly as follows. Proposition 4. For n ≥ 4, [

En =

C(Ta,r , Ua,r ),

(a,r)̸=(1,0)

where a ∈ F× 2n and 0 ≤ r < n. Proof. Suppose first that A ∈ En . Then Stab(ΦA ) contains some nonidentity T ∈ GLn (F2 ). Since T ◦ A ◦ J = A ◦ J ◦ T, we have J ◦ T = (A−1 T A) ◦ J. By Theorem 3, there exist a ∈ F× 2n and 0 ≤ r < n such that T = Ta,r ,

A−1 Ta,r A = Ua,r .

Because T ̸= I, we have (a, r) ̸= (1, 0). Hence A ∈ C(Ta,r , Ua,r ). Conversely, suppose that A ∈ C(Ta,r , Ua,r ) for some (a, r) ̸= (1, 0). Then A−1 Ta,r A = Ua,r , and, by Theorem 3, J ◦ Ta,r = Ua,r ◦ J. Combining these identities gives Ta,r ◦ A ◦ J = A ◦ J ◦ Ta,r . Thus Ta,r ∈ Stab(ΦA ). Since (a, r) ̸= (1, 0), we have Ta,r ̸= I, so A ∈ En . Hence, estimating pn reduces to controlling the sizes of these conjugator sets. The structural results needed for this counting problem are developed in the next section. 4

3

Structural Lemmas for the Exceptional Set

Proposition 4 expresses the exceptional set as a union of semilinear conjugator sets. We now develop the structural lemmas needed to control the size of these sets and to identify the largest contributions to En . For T ∈ GLn (F2 ), let CGLn (F2 ) (T ) = {A ∈ GLn (F2 ) : AT = T A} denote the group centralizer of T . We also write Z(T ) = {L ∈ EndF2 (F2n ) : LT = T L} for its centralizer algebra. These two objects are related by CGLn (F2 ) (T ) = Z(T )× . The connection with the conjugator sets from the previous section is straightforward but important. If C(T, U ) ̸= ∅, then C(T, U ) is a coset of CGLn (F2 ) (T ). In particular, |C(T, U )| = |CGLn (F2 ) (T )|. Thus, controlling the sizes of the conjugator sets reduces to understanding the centralizers of the semilinear maps Ta,r . The upper bound for pn will follow by summing the sizes of the conjugator sets appearing in Proposition 4. Since a nonempty conjugator set has the same cardinality as the corresponding group centralizer, it remains to control CGLn (F2 ) (Ta,r ). We do this through the centralizer algebra Z(Ta,r ). For the upper bound on pn , it is enough to obtain a uniform bound on the dimension of Z(Ta,r ). The exact dimension formula is more refined, we state it below and provide its proof in Appendix A. For 0 ≤ r < n, set dr = gcd(n, r), and let za,r = NF2n /F2dr (a) ∈ F× 2dr be the relative norm of a from F2n to F2dr . Finally, define ea,r = [F2 (za,r ) : F2 ]. Proposition 5.

For a ∈ F× 2n and 0 ≤ r < n, dimF2 Z(Ta,r ) =

n dr . ea,r

Proof. See Appendix A. The exact formula immediately yields the uniform estimate needed for the upper bound on pn . Lemma 6. For every (a, r) ̸= (1, 0), dimF2 Z(Ta,r ) ≤

n2 . q(n)

Proof. If r = 0, then a ̸= 1. Hence ea,0 = [F2 (a) : F2 ] > 1. Since ea,0 | n, we have ea,0 ≥ q(n), and therefore dimF2 Z(Ta,0 ) =

n2 n2 ≤ . ea,0 q(n)

If 1 ≤ r < n, then dr = gcd(n, r) is a proper divisor of n, so n dr ≤ . q(n) Since ea,r ≥ 1, dimF2 Z(Ta,r ) =

n dr n2 ≤ ndr ≤ . ea,r q(n)

5

Remark 7. Since CGLn (F2 ) (Ta,r ) = Z(Ta,r )× , we obtain

2

|CGLn (F2 ) (Ta,r )| ≤ |Z(Ta,r )| = 2dimF2 Z(Ta,r ) ≤ 2n /q(n) . The preceding lemma shows that every nontrivial semilinear candidate has centralizer dimension at most n2 /q(n). To obtain a matching lower bound for pn , we now show that this scale is realized by a natural family arising from the Frobenius symmetry of inversion. Let n , τ = σm . m= q(n) Since τ = σ m is an F2 -linear automorphism, we may view τ as an element of GLn (F2 ). Moreover, τ has order q(n), and its fixed field F2m has maximal size among the proper subfields of F2n . Lemma 8. If A ∈ CGLn (F2 ) (τ ), then A ∈ En . Hence CGLn (F2 ) (τ ) ⊆ En . Proof. Since τ commutes with both A and J, τ ◦ A ◦ J = A ◦ τ ◦ J = A ◦ J ◦ τ. Thus τ ∈ Stab(ΦA ). Because τ ̸= I, we have A ∈ En . It remains to estimate the size of CGLn (F2 ) (τ ). The key point is that the action of τ admits a natural module description over the group algebra of the cyclic group generated by τ . The following structural description provides a convenient way to estimate the lower bound. Since its proof is relatively long and technical, and is not central to the main argument, we provide it in Appendix B. Let ⟨τ ⟩ denote the cyclic group generated by τ . Since τ has order q(n), this group has order q(n). Let R = F2 [⟨τ ⟩] be the group algebra of ⟨τ ⟩ over F2 . We use the R-module structure induced by the action of ⟨τ ⟩ to estimate CGLn (F2 ) (τ ). Proposition 9. Under the natural R-module structure on F2n induced by the action of ⟨τ ⟩, F2n ∼ = Rm , Consequently,

m=

n . q(n)

Z(τ ) ∼ = Mm (R),

where Mm (R) denotes the ring of m × m matrices with entries in R. Moreover, CGLn (F2 ) (τ ) ∼ = GLm (R). Proof. See Appendix B. The preceding proposition reduces the lower-bound problem to comparing the number of invertible matrices over R with the total number of matrices over R. Let ∞ Y κ= (1 − 2−j ). j=1

The following lemma gives the required lower bound on the proportion of invertible matrices in Mm (R). 6

Lemma 10. With R = F2 [⟨τ ⟩], |CGLn (F2 ) (τ )| = |GLm (R)| ≥ κq(n) |Mm (R)|. Proof. Since

R = F2 [⟨τ ⟩] ∼ = F2 [x]/(xq(n) − 1),

we distinguish the cases q(n) odd and q(n) = 2. Suppose first that q(n) is odd. Then xq(n) − 1 is square-free over F2 . Hence R∼ =

s Y

F2fi

i=1

for some positive integers f1 , . . . , fs , with s ≤ q(n). It follows that Mm (R) ∼ =

s Y

Mm (F2fi )

i=1

and GLm (R) ∼ =

s Y

GLm (F2fi ).

i=1

Therefore

Since fi ≥ 1,

s m
|GLm (R)| Y Y 1 − 2−fi j . = |Mm (R)| i=1 j=1 m Y

∞
Y
1 − 2−fi j ≥ 1 − 2−j = κ,

j=1

j=1

and hence

|GLm (R)| ≥ κs ≥ κq(n) . |Mm (R)|

Now suppose that q(n) = 2. Then

R∼ = F2 [x]/((x + 1)2 ).

Let m be the ideal generated by the image of x + 1. Then R/m ∼ = F2 . Since R is a local ring, an element of R is a unit if and only if its image in R/m is nonzero. Therefore, for A ∈ Mm (R), A ∈ GLm (R) ⇐⇒ det(A) ∈ R× ⇐⇒ det(A) ̸= 0, where A denotes the image of A in Mm (R/m). Hence A is invertible over R if and only if A is invertible over F2 . Consequently, m Y |GLm (F2 )| |GLm (R)| = = (1 − 2−j ) ≥ κ ≥ κq(n) . |Mm (R)| |Mm (F2 )| j=1

Thus |GLm (R)| ≥ κq(n) |Mm (R)|. Since |CGLn (F2 ) (τ )| = |GLm (R)|, the result follows.

7

Remark 11. Since R = F2 [⟨τ ⟩] has

|R| = 2q(n) ,

we have

2

2

2

|Mm (R)| = |R|m = 2q(n)m = 2n /q(n) . Therefore, 2

|CGLn (F2 ) (τ )| = |GLm (R)| ≥ κq(n) 2n /q(n) . We have now obtained the two structural estimates needed for the main probabilistic result. On the upper-bound side, every nontrivial semilinear candidate satisfies dimF2 Z(Ta,r ) ≤ and therefore

n2 , q(n) 2

|CGLn (F2 ) (Ta,r )| ≤ 2n /q(n) . On the lower-bound side, the Frobenius automorphism τ = σ n/q(n) produces a natural family of exceptional outer linear transformations. Since 2

|Mm (R)| = 2n /q(n) , we have

2

|CGLn (F2 ) (τ )| ≥ κq(n) 2n /q(n) . 2

Thus the upper and lower estimates are governed by the same centralizer scale 2n /q(n) . We now combine these bounds to prove the main theorem.

4

Proof of the Main Theorem

We now combine the structural estimates from the previous section to obtain matching upper and lower bounds for pn . Main Theorem. For n ≥ 4, 2

κq(n) 2−n (1−1/q(n)) ≤ pn ≤ where κ=

∞ Y

n −n2 (1−1/q(n))+n 2 , κ

(1 − 2−j ).

j=1

Proof. We first prove the upper bound. By Proposition 4, [ En = C(Ta,r , Ua,r ). (a,r)̸=(1,0)

Hence |En | ≤

X

|C(Ta,r , Ua,r )|.

(a,r)̸=(1,0)

Whenever C(Ta,r , Ua,r ) is nonempty, it has the same cardinality as CGLn (F2 ) (Ta,r ). By Lemma 6, 2

|CGLn (F2 ) (Ta,r )| ≤ 2n /q(n) .

8

There are n(2n − 1) − 1 < n2n nontrivial pairs (a, r). Therefore 2

|En | < n2n 2n /q(n) . Since |GLn (F2 )| = 2n

2

n Y

2

(1 − 2−j ) ≥ κ 2n ,

j=1

we obtain pn =

2 n |En | ≤ 2−n (1−1/q(n))+n . |GLn (F2 )| κ

For the lower bound, let m=

n , q(n)

τ = σm .

By Lemma 8, CGLn (F2 ) (τ ) ⊆ En . Hence pn ≥

|CGLn (F2 ) (τ )| . |GLn (F2 )|

By Lemma 10, 2

|CGLn (F2 ) (τ )| ≥ κq(n) 2n /q(n) . Since

2

|GLn (F2 )| ≤ 2n , it follows that

2

pn ≥ κq(n) 2−n (1−1/q(n)) . This proves the theorem. The two-sided estimate in Main Theorem determines the leading quadratic exponent of the exceptional probability. Taking logarithms gives the following asymptotic form. Corollary 12. For n ≥ 4,  − log2 pn = n 1 − 2

1 q(n)

 + O(n).

Proof. Taking − log2 of the two-sided bound in the Main Theorem reverses the inequalities and gives   1 n − n − log2 ≤ − log2 pn n2 1 − q(n) κ and

 − log2 pn ≤ n 1 − 2

1 q(n)

Since q(n) ≤ n, both error terms are O(n). Therefore  2 − log2 pn = n 1 −

9

 + q(n) log2

1 q(n)

 + O(n).

1 . κ

n

q(n)

n2 (1 − 1/q(n))

4

2

8

5 6 7 8

5 2 7 2

20 18 42 32

pn or theorem bounds 5 p4 = ≈ 2.98 × 10−2 168 1.92 × 10−9 ≤ p5 ≤ 5.28 × 10−4 3.18 × 10−7 ≤ p6 ≤ 5.07 × 10−3 3.81 × 10−17 ≤ p7 ≤ 7.05 × 10−10 1.94 × 10−11 ≤ p8 ≤ 1.65 × 10−6

Table 1: Small-dimensional values and bounds for the exceptional probability pn . Remark 13. The quadratic exponent is determined by the smallest prime divisor of n. If n is even, then q(n) = 2, and n2 − log2 pn = + O(n). 2 If n is prime, then q(n) = n, and − log2 pn = n2 − n + O(n) = n2 + O(n). Thus the probability that a random outer linear transformation preserves a nontrivial linear self-symmetry of inversion is exponentially small in n2 , with a leading exponent determined by the arithmetic of the dimension through q(n). The matching lower bound shows that this exponent is not an artifact of the upper-bound argument. It is already realized by the Frobenius symmetry associated with a proper subfield of maximal size. Table 1 illustrates the theorem for 4 ≤ n ≤ 8. For n = 4, exhaustive enumeration gives the exact value p4 = 5/168; for n = 5, 6, 7, 8, we report the bounds from Main Theorem.

5

Cryptographic Applications

The preceding results describe how frequently a linear self-symmetry of inversion survives after an outer linear transformation. In this section, we turn to concrete cryptographic applications. We first derive a simple rigidity criterion based on the coefficient relations arising from the stabilizer condition. The criterion depends on only two coefficients of the linearized polynomial of the outer linear map. We then apply it to the AES S-box. After that, we discuss how such self-symmetries can interact with diffusion layers in iterative constructions, with ARIA and Vision as examples. A General Rigidity Criterion. map A as

Let n ≥ 4, and write the linearized polynomial of an invertible F2 -linear A(x) =

n−1 X

i

λ i x2 .

i=0

Proposition 14. Suppose that λ0 λ1 ̸= 0, and set ρ=

λ21 . λ30

If ρ does not belong to any proper subfield of F2n , then Stab(A ◦ J) = {I}. Proof. Let T ∈ Stab(A ◦ J). By Theorem 3, there exist a ∈ F× 2n and 0 ≤ r < n such that T = Ma σ r and A−1 Ma σ r A = Ma−1 σ r . 10

Equivalently, Ma σ r A = AMa−1 σ r . Expanding both sides gives n−1 X

r

i+r

aλ2i x2

=

n−1 X

i=0

i

λi a−2 x2

i+r

.

i=0

Since i 7→ i + r (mod n) permutes the Frobenius exponents, comparison of coefficients gives r

i

a2 +1 = λi1−2 for every i with λi ̸= 0. In particular, r

r

a2 = λ01−2 ,

a3 = λ11−2 .

Therefore

r

ρ 1−2 = 1, and hence

r

ρ2 = ρ. If r ̸= 0, then ρ ∈ F2gcd(n,r) , which is a proper subfield of F2n , contradicting the hypothesis. Thus r = 0. The relation for i = 0 then gives a2 = 1, so a = 1. Hence T = I, and therefore Stab(A ◦ J) = {I}.

The AES S-box.

We now apply Proposition 14 to the AES S-box [15]. In the standard field representation F28 = F2 [t]/(t8 + t4 + t3 + t + 1),

the linear part of the AES affine transformation has linearized polynomial AAES (x) =

7 X

i

λ i x2 ,

i=0

with (λ0 , . . . , λ7 ) = (05, 09, F 9, 25, F 4, 01, B5, 8F ). For the first two coefficients, ρ=

λ21 = E7. λ30

Every proper subfield of F28 is contained in F24 . Since E715 = 35 ̸= 1, we have E7 ∈ / F24 . Hence E7 belongs to no proper subfield of F28 . Proposition 14 therefore gives Stab(AAES ◦ J8 ) = {I}. The full AES S-box is SAES (x) = AAES (J8 (x)) + c, where c = 63 in hexadecimal notation.

11

Corollary 15. The full AES S-box has no nontrivial linear self-symmetry: Stab(SAES ) = {I}. Proof. Let T ∈ Stab(SAES ). Evaluating T ◦ SAES = SAES ◦ T at 0 gives T (c) = c. The constant terms therefore cancel, and T ∈ Stab(AAES ◦ J8 ). Hence T = I. Thus the AES affine layer satisfies the two-coefficient criterion, and the resulting S-box has no nontrivial linear self-symmetry. We next examine why such S-box-level self-symmetries can matter at the level of an iterative cipher. ARIA and Binary Diffusion. S-box. The second is

ARIA [12] uses two S-boxes and their inverses. The first, S1 , is the AES
S2 (x) = B x247 + c,

for an affine layer with linear part B. Since x247 = x−8 = σ 3 (J(x)), the nonconstant part of S2 belongs to the family considered here, with outer linear layer B ◦ σ 3 . The diffusion layer of ARIA is a 16 × 16 binary matrix acting on bytes. Hence any F2 -linear map applied identically to each byte commutes with this diffusion layer. Therefore, a byte-wise linear self-symmetry that survives the S-box layer is not destroyed by the diffusion layer and may continue through the round structure if it is also compatible with the remaining round operations. For ARIA, S-box rigidity is therefore the natural condition that prevents such byte-wise linear selfsymmetries from propagating through the diffusion layer. Corollary 15 already gives this rigidity for S1 . A Large-Field Example: Vision. The Vision cipher [1] uses S-boxes obtained by composing inversion over a binary field with an F2 -linearized affine permutation. Writing the linear part as A(x) = b1 x + b2 x2 + b3 x4 , the transformed inverse A ◦ J belongs directly to the family studied in this paper. This example is different from the byte-oriented setting of AES and ARIA. The field dimension is much larger, while the outer linear map has a sparse linearized representation. In this setting, Proposition 14 gives a particularly simple rigidity test. A ◦ J is rigid whenever b22 b31 lies in no proper subfield of F2n , provided that b1 b2 ̸= 0. Thus the criterion is not limited to small S-boxes. It also applies naturally to inverse-based nonlinear layers over larger binary fields, where sparsity of the outer linearized polynomial makes the rigidity condition especially easy to check. For such large-field constructions, rigidity is a desirable structural property. It rules out nontrivial linear self-symmetries inherited from finite-field inversion. This does not by itself imply cryptographic security, but it removes one possible source of algebraic structure that could otherwise persist through an iterated construction. Related Inverse-Based Constructions. The framework also applies directly to inverse-based S-boxes with linear transformations on both sides of inversion. Suppose S = B ◦ J ◦ A,

A, B ∈ GLn (F2 ).

Then A ◦ S ◦ A−1 = (AB) ◦ J, 12

and therefore Stab(S) = A−1 Stab((AB) ◦ J)A. Thus S is rigid if and only if (AB) ◦ J is rigid. In particular, two-sided linear transformations around inversion reduce directly to the outer-linear setting studied in this paper. Additive constants after inversion can be handled as in Corollary 15. If a constant is added before inversion, as in Camellia [14] and SM4 [7], one must conjugate by an affine map. A linear self-symmetry of the original S-box is then transformed into an affine self-symmetry of a map of the form (AB) ◦ J + c. Thus the linear part is covered by the present theory, while the additional affine condition can be checked separately.

6

Conclusion

We studied the linear self-symmetries of finite-field inversion after composition with an outer invertible linear transformation. We showed that the exceptional probability satisfies   1 2 + O(n), − log2 pn = n 1 − q(n) so the leading quadratic exponent is determined by the smallest prime divisor q(n) of the extension degree. The cryptographic examples illustrate how this symmetry question appears in practice. The AES S-box satisfies a simple rigidity criterion, ARIA shows how byte-wise symmetries can pass through binary diffusion layers, and Vision extends the setting to larger binary fields with sparse linearized outer maps. The same framework also extends directly to two-sided linear transformations around inversion, covering the linear parts of related constructions such as Camellia and SM4.

References [1] Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, and Alan Szepieniec. Design of symmetric-key primitives for advanced cryptographic protocols. IACR Transactions on Symmetric Cryptology, 2020(3):1–45, 2020. [2] Elad Barkan and Eli Biham. In how many ways can you write Rijndael? In Advances in Cryptology – ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 160–175. Springer, 2002. [3] Alex Biryukov, Christophe De Cannière, An Braeken, and Bart Preneel. A toolbox for cryptanalysis: Linear and affine equivalence algorithms. In Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 33–50. Springer, 2003. [4] Anne Canteaut and Léo Perrin. On CCZ-equivalence, extended-affine equivalence, and function twisting. Finite Fields and Their Applications, 56:209–246, 2019. [5] Claude Carlet, Pascale Charpin, and Victor Zinoviev. Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography, 15(2):125–156, 1998. [6] Xi Chen, Longjiang Qu, Shaojing Fu, and Chao Li. The number of affine equivalent classes and extended affine equivalent classes of vectorial boolean functions. Discrete Applied Mathematics, 289:477–491, 2021. [7] International Organization for Standardization. Information technology—security techniques— encryption algorithms—part 3: Block ciphers—amendment 1: Sm4. Technical Report 180333:2010/Amd 1:2021, ISO/IEC, 2021. [8] Keita Ishizuka. Almost all vectorial functions have trivial extended-affine stabilizers, 2026. arXiv:2602.06668. https://arxiv.org/abs/2602.06668. 13

[9] Selçuk Kavut. Results on rotation-symmetric S-boxes. Information Sciences, 201:93–113, 2012. [10] Lukas Kölsch. On CCZ-equivalence of the inverse function. IEEE Transactions on Information Theory, 67(7):4856–4862, 2021. [11] Gregor Leander, Mohamed Ahmed Abdelraheem, Hoda AlKhzaimi, and Erik Zenner. A cryptanalysis of PRINTcipher: The invariant subspace attack. In Advances in Cryptology – CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science. Springer, 2011. [12] Jaechul Lee, Jung Hee Lee, Jong-Sung Kim, Daesung Kwon, and Changhoon Kim. A description of the aria encryption algorithm. Technical Report RFC 5794, Internet Engineering Task Force, 2010. [13] Jingmei Liu, Baodian Wei, Xiangguo Cheng, and Xinmei Wang. Cryptanalysis of Rijndael S-box and improvement. Applied Mathematics and Computation, 170(2):958–975, 2005. [14] M. Matsui, J. Nakajima, and S. Moriai. A description of the camellia encryption algorithm. RFC 3713, Internet Engineering Task Force, 2004. [15] National Institute of Standards and Technology. Advanced encryption standard (aes). Federal Information Processing Standards Publication 197-upd1, National Institute of Standards and Technology, 2023. [16] Tron Omland and Pantelimon Stănică. Permutation rotation-symmetric S-boxes, liftings and affine equivalence, 2022. arXiv:2203.00778. [17] Adrian Ranea and Bart Preneel. On self-equivalence encodings in white-box implementations. In Selected Areas in Cryptography – SAC 2020, volume 12804 of Lecture Notes in Computer Science, pages 639–669. Springer, 2021. [18] Vincent Rijmen, Paulo S. L. M. Barreto, and Décio L. Gazzoni Filho. Rotation symmetry in algebraically generated cryptographic substitution tables. Information Processing Letters, 106(6):246–250, 2008. [19] Joachim Rosenthal. A polynomial description of the Rijndael advanced encryption standard. Journal of Algebra and Its Applications, 2(2):223–236, 2003. [20] Feng Yuan, Ji-Jun Jiang, Yang Yang, Hai-Wen Ou, and Min-Juan Wang. Enumeration of cryptographic functions affine equivalent to the inverse function over Fpn . Chinese Journal of Computers, 42(5):1126– 1136, 2019.

A

Proof of Proposition 5

To prove Proposition 5, we first isolate the finite-field equation that governs each coefficient of a commuting linearized polynomial. Lemma 16. Let 0 ≤ r < n, let dr = gcd(n, r), and let η ∈ F× 2n . Set r

Vη = {u ∈ F2n : u2 = ηu}. Then Vη contains a nonzero element if and only if NF2n /F2dr (η) = 1. When this condition holds, Vη is one-dimensional over F2dr , and hence dimF2 Vη = dr . Otherwise, Vη = {0}.

14

Proof. If r = 0, then dr = n, and the equation becomes u = ηu. Thus Vη = F2n when η = 1, and Vη = {0} otherwise, which agrees with the stated norm condition. Now assume 1 ≤ r < n. Since dr = gcd(n, r), the fixed field of σ r is F2dr . Moreover, σ r has order n/dr and generates Gal(F2n /F2dr ). Hence Vη is an F2dr -subspace of F2n . If u0 , u ∈ Vη are nonzero, then 

u u0

2r =

u , u0

so u/u0 ∈ F2dr . Therefore, whenever Vη contains a nonzero element, it is one-dimensional over F2dr . It remains to determine when a nonzero solution exists. For u ̸= 0, r

u2 = ηu

⇐⇒

r

η = u2 −1 .

By the finite-field form of Hilbert’s Theorem 90, this occurs if and only if NF2n /F2dr (η) = 1. Therefore, when the norm condition holds, dimF2 Vη = dr , and otherwise Vη = {0}. We now apply Lemma 16 coefficientwise to determine the centralizer algebra Z(Ta,r ). Proof of Proposition 5. Every F2 -linear map L : F2n → F2n has a unique linearized polynomial representation n−1 X i ℓi x2 , L(x) = ℓi ∈ F2n . i=0

Since

r

Ta,r (x) = ax2 , we obtain L ◦ Ta,r (x) =

n−1 X

i

i+r

r

i+r

ℓi a2 x2

,

i=0

whereas Ta,r ◦ L(x) =

n−1 X

aℓ2i x2

.

i=0

Because addition by r permutes the Frobenius exponents modulo n, uniqueness of the linearized polynomial representation gives r i L ◦ Ta,r = Ta,r ◦ L ⇐⇒ ℓ2i = a2 −1 ℓi (0 ≤ i < n). Thus the centralizer condition reduces to n independent equations, one for each coefficient ℓi . Applying i Lemma 16 with η = a2 −1 , the i-th coefficient admits a nonzero solution if and only if
i NF2n /F2dr a2 −1 = 1. Using multiplicativity of the norm and the definition of za,r , we obtain
i i 2i −1 NF2n /F2dr a2 −1 = NF2n /F2dr (a)2 −1 = za,r . 15

Hence the norm condition is equivalent to i

2 −1 za,r = 1,

or equivalently, i

2 za,r = za,r . i

2 Now ea,r = [F2 (za,r ) : F2 ], so za,r = za,r holds exactly when ea,r | i. Moreover, za,r ∈ F2dr , so ea,r | dr , and hence ea,r | n. Therefore exactly n/ea,r indices i ∈ {0, . . . , n − 1} satisfy the norm condition. For each such index, Lemma 16 gives a dr -dimensional F2 -solution space for ℓi . For all remaining indices, only ℓi = 0 is possible. Since the coefficient equations are independent,

dimF2 Z(Ta,r ) =

B

n ea,r

dr =

n dr . ea,r

Proof of Proposition 9

Recall that m=

n , q(n)

τ = σm ,

so that τ has order q(n) and fixes F2m . Let R = F2 [⟨τ ⟩]. The action of ⟨τ ⟩ on F2n gives F2n a natural R-module structure. Proof of Proposition 9. Consider the Galois extension F2n /F2m . Its Galois group is
Gal F2n /F2m = ⟨τ ⟩, which has order q(n). By the Normal Basis Theorem, F2n is a free module of rank one over F2m [⟨τ ⟩]. Equivalently, F2n ∼ = F2m [⟨τ ⟩] as F2m [⟨τ ⟩]-modules. Since R = F2 [⟨τ ⟩] and F2m has dimension m over F2 , we have, as R-modules, F2m [⟨τ ⟩] ∼ = F2m ⊗F2 R ∼ = Rm . Hence

F2n ∼ = Rm

as R-modules. Now let Z(τ ) = {L ∈ EndF2 (F2n ) : Lτ = τ L}. Because R is generated over F2 by the action of τ , an F2 -linear map commutes with τ if and only if it is R-linear. Therefore Z(τ ) = EndR (F2n ). Using the R-module isomorphism above, Z(τ ) ∼ = EndR (Rm ) ∼ = Mm (R). Here R is commutative, since ⟨τ ⟩ is cyclic. Finally, CGLn (F2 ) (τ ) = Z(τ )× ,

16

because the group centralizer consists precisely of the invertible F2 -linear maps in Z(τ ). Under the isomorphism Z(τ ) ∼ = Mm (R), the invertible elements correspond to the invertible m × m matrices over R. Thus CGLn (F2 ) (τ ) ∼ = GLm (R).

17

Related documents

• Linear Self-Symmetries of Inverse-Based S-boxes: Generic Rigidity and Applications#1414442
• The OCB Authenticated-Encryption Algorithm#399111
• Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness#997600
• Image Encryption Algorithm Based on Convolutional Neural Networks and Dynamic S-Box Generation#290517
• Computer Aided Cryptanalysis from Ciphers to Side Channels#1100255