Source-linked AI summary
Linear Self-Symmetries of Inverse-Based S-boxes: Generic Rigidity and Applications
Zheng Zhang, Na Zhang
TL;DR
The paper asks how often an outer linear layer preserves a nontrivial self-symmetry of inversion, a question earlier works had not resolved in relation to the arithmetic of the extension degree. It uses the classification of two-sided linear equivalences and centralizer estimates to study this probability. The resulting leading quadratic exponent depends on the extension degree’s smallest prime divisor.
Problem
Earlier works do not determine how often a nontrivial linear self-symmetry survives or how that frequency depends on the arithmetic of n.
Source: §1 · pp. 1–2Method
Results
The probability is exponentially small in n^2, with leading exponent n^2/2 for even n and n^2 for prime n.
Source: §1 · p. 3, §4 · p. 10, §6 · p. 13Takeaways & Limitations
The applications include a rigidity criterion for AES, byte-wise symmetry propagation through ARIA diffusion, and Vision over larger binary fields.
Source: §5 · p. 12, §6 · p. 13One application statement is scoped to ρ outside every proper subfield of F2^n.
Source: §5 · p. 10
Abstract
from arXiv · showhide
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 \(GL_n(\mathbb F_2)\). 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.
1 Introduction
The paper asks how often an outer linear layer preserves a nontrivial linear self-symmetry of finite-field inversion, a question not answered by prior work on equivalence or symmetry classifications. It gives matching bounds whose leading quadratic exponent depends on the smallest prime divisor of the extension degree, and connects the result to inverse-based S-boxes.
1 Introduction
- For a uniformly chosen outer linear map, the paper studies the probability that the transformed inversion map retains a nontrivial linear self-symmetry.A linear self-symmetry uses the same linear map on both sides; this differs from linear self-equivalence, which permits separate input and output maps.Source: §1 · pp. 1–2
- Prior work classifies equivalences and studies algebraic S-box symmetries, but does not determine the survival frequency in this structured family or its dependence on n.The paper distinguishes its question from generic stabilizer triviality in the full space of vectorial functions.Source: §1 · p. 2
- The matching bounds determine a leading quadratic exponent governed by the smallest prime divisor q(n): it is n^2/2 for even n and n^2 for prime n.The decay rate therefore depends on the arithmetic of the extension degree, not only its dimension.Source: §1 · pp. 2–3
- For designers seeking rigidity, the theorem says a generic outer layer removes all such symmetries, while n = 4 and n = 8 are in the least favorable case q(n) = 2.The latter motivates direct checks for concrete constructions.Source: §1 · p. 3
- The applications include a rigidity criterion, the AES S-box, propagation through ARIA diffusion, Vision, and related inverse-based constructions Camellia and SM4.The paper also frames self-symmetries as potentially persistent across iterative rounds when compatible with the S-box, diffusion layer, and round constants.Source: §1 · pp. 2–3
2 Notation and Inversion Symmetries
The section sets up inversion and its Frobenius symmetries, then uses a classification of two-sided linear equivalences to reduce surviving self-symmetries to semilinear conjugacy. The resulting probability problem is expressed through the sizes of conjugator sets.
2 Notation and Inversion Symmetries
- The inverse map J on F2^n is extended by J(0) = 0, and the section fixes notation for the linear stabilizer and the probability p_n.A nontrivial stabilizer element is a nonidentity linear self-symmetry; p_n is the probability that a uniform outer linear map leaves one in A ◦ J.Source: §2 · p. 3
- Inversion commutes with Frobenius, so the powers of σ(x) = x^2 are linear symmetries of J.This inherent symmetry supplies the starting candidates for symmetries that may survive an outer map.Source: §2 · p. 3
- The classification by Yuan et al. lists the two-sided linear equivalences of J as semilinear pairs built from field multiplication and Frobenius powers.In the section’s notation, T_a,r = M_a ◦ σ^r and U_a,r = M_a−1 ◦ σ^r.Source: §2 · pp. 3–4
- Every linear self-symmetry of A ◦ J must arise from one of those pairs, reducing the survival test to whether A conjugates T_a,r to U_a,r.The relevant outer transformations form conjugator sets, whose sizes control p_n.Source: §2 · p. 4
3 Structural Lemmas for the Exceptional Set
The structural estimates reduce the exceptional-set count to centralizers of semilinear maps. A uniform upper estimate and a Frobenius-derived lower-bound family share the scale determined by q(n).
3 Structural Lemmas for the Exceptional Set
- A nonempty conjugator set is a coset of the corresponding group centralizer, so its cardinality equals that centralizer’s size.Thus estimating the exceptional probability reduces to controlling centralizers of the semilinear candidates.Source: §3 · p. 5
- Every nontrivial semilinear candidate has centralizer dimension at most n^2/q(n), giving the uniform scale needed for the upper bound.The section obtains this through the centralizer algebra and a bound on its dimension.Source: §3 · pp. 5, 6, 8
- A Frobenius power τ = σ^(n/q(n)) has order q(n) and fixes the largest proper subfield, producing a natural family in the exceptional set.For this nonidentity τ, outer maps commuting with τ belong to the exceptional set.Source: §3 · p. 6
- The lower-bound estimate uses the module structure induced by the cyclic group generated by τ to estimate its centralizer.The section describes F2^n as a module over the group algebra and reduces the count to invertible matrices over that algebra.Source: §3 · p. 6
- The upper and lower estimates are governed by the same centralizer scale, 2^(n^2/q(n)), establishing a common scale for the bounds.Source: §3 · pp. 6, 8
4 Proof of the Main Theorem
The proof combines an upper bound over semilinear conjugator sets with a lower bound from a Frobenius family. Together they yield matching bounds and the leading quadratic exponent for the exceptional probability.
4 Proof of the Main Theorem
- The upper bound sums conjugator-set sizes, using that each nonempty set has the corresponding semilinear map’s centralizer size.The proof bounds the exceptional-set size by |E_n| < n^2 2^(n^2/q(n)).Source: §4 · pp. 8–9
- The lower bound selects τ = σ^(n/q(n)) and counts outer maps commuting with this nonidentity Frobenius power.Those maps lie in the exceptional set, yielding the matching lower estimate.Source: §4 · p. 9
- The matching upper and lower bounds show that p_n is exponentially small in n^2, with leading exponent determined by q(n), the smallest prime divisor of n.The matching lower bound shows the exponent is realized by the Frobenius symmetry associated with a maximal proper subfield, not merely by the upper-bound argument.Source: §4 · pp. 8–10
- For n = 4, exhaustive enumeration gives the exact exceptional probability p_4 = 5/168; for n = 5, 6, 7, and 8, the paper reports theorem bounds.Table 1 presents the small-dimensional values and bounds.Source: §4 · p. 10, Table 1 · p. 10
5 Cryptographic Applications
The applications use a two-coefficient rigidity criterion to analyze inverse-based S-boxes, establish that the full AES S-box has no nontrivial linear self-symmetry, and examine ARIA, Vision, and related constructions.
A General Rigidity Criterion
- The general rigidity criterion depends on only two coefficients of the outer linear map's linearized polynomial.The paper applies the criterion to inverse-based S-boxes, including cases with sparse linearized representations.Source: §5 · p. 10
The AES S-box
- The AES affine layer satisfies the two-coefficient criterion, so the full AES S-box has no nontrivial linear self-symmetry.The argument uses the AES affine transformation's linearized-polynomial coefficients and the fact that E7 belongs to no proper subfield of F28.Source: §5 · pp. 11–12
ARIA and Binary Diffusion
- In ARIA, a byte-wise linear self-symmetry surviving the S-box layer also commutes with the diffusion layer, so rigidity of S1 prevents that propagation route.ARIA's S1 is the AES S-box, for which the paper establishes rigidity.Source: §5 · p. 12
A Large-Field Example: Vision
- For Vision's larger binary fields, A ◦J is rigid when the tested coefficient lies in no proper subfield and b1b2 ≠ 0.The paper presents this as a rigidity test for inverse-based nonlinear layers whose outer linearized polynomial is sparse; rigidity removes one possible source of algebraic structure, not a guarantee of security.Source: §5 · pp. 10–12
Related Inverse-Based Constructions
- Two-sided linear transformations around inversion reduce to the outer-linear setting, while a constant added before inversion requires an affine self-symmetry condition checked separately.The linear part is covered by the framework; the additional affine condition is separate.Source: §5 · p. 13
6 Conclusion
The exceptional probability for a nontrivial linear self-symmetry of transformed inversion has a leading quadratic exponent determined by the smallest prime divisor of the extension degree. The paper also applies its framework to several cryptographic constructions.
6 Conclusion
- The leading quadratic exponent of the exceptional probability is determined by the smallest prime divisor q(n) of the extension degree.The probability concerns whether a uniformly chosen outer linear transformation leaves a nontrivial linear self-symmetry.Source: §6 · p. 13
- The AES S-box satisfies a rigidity criterion, while ARIA and Vision illustrate the framework for other inverse-based constructions.The framework also extends to two-sided linear transformations around inversion, including the linear parts of Camellia and SM4.Source: §6 · p. 13
A Proof of Proposition 5
The proof determines the centralizer by representing linear maps as linearized polynomials and solving independent coefficient equations. A finite-field norm condition controls which coefficients can be nonzero and the dimensions of their solution spaces.
A Proof of Proposition 5
- The proof first isolates the finite-field equation governing each coefficient of a commuting linearized polynomial.The coefficient equations arise from the centralizer condition.Source: A Proof of Proposition 5 · pp. 14–15
- When r = 0, Vη equals F2^n if η = 1 and equals {0} otherwise.This case agrees with the stated norm condition.Source: A Proof of Proposition 5 · p. 15
- For 1 ≤ r < n, Vη is an F2^dr-subspace, and any nonzero such space is one-dimensional over F2^dr.Here dr = gcd(n, r), and the fixed field of the corresponding Frobenius map is F2^dr.Source: A Proof of Proposition 5 · p. 15
- A coefficient equation has a nonzero solution exactly when its norm condition holds; otherwise its solution space is {0}.When nonzero solutions exist, Vη is one-dimensional over F2^dr.Source: A Proof of Proposition 5 · pp. 14–15
- The centralizer condition reduces to n independent equations, one for each coefficient of a linearized polynomial.Each coefficient equation is solved using the finite-field norm condition.Source: A Proof of Proposition 5 · p. 15
- Exactly n/e_a,r coefficient indices satisfy the norm condition, each contributing a dr-dimensional F2-solution space.All other coefficient equations force the coefficient to be zero.Source: A Proof of Proposition 5 · p. 16
B Proof of Proposition 9
The proof computes a group centralizer by viewing the field extension as a module for the cyclic group generated by τ. Commuting linear maps are then identified with module endomorphisms.
B Proof of Proposition 9
- The normal basis theorem gives F2^n a free rank-one module structure over F2^m[⟨τ⟩].The Galois group in this extension has order q(n).Source: B Proof of Proposition 9 · p. 16
- An F2-linear map commutes with τ exactly when it is R-linear, where R = F2[⟨τ⟩].This turns the centralizer computation into an R-module endomorphism calculation.Source: B Proof of Proposition 9 · p. 16
- Since R is commutative, the centralizer algebra is identified with m × m matrices over R, whose invertible elements give the group centralizer.The group centralizer consists of the invertible F2-linear maps in Z(τ).Source: B Proof of Proposition 9 · pp. 16–17