CS Paper Radar

Basis Rigidity of the AES S-box and Generic Rigidity of Inversion under Affine Transformations

Zheng Zhang, Na Zhang

cs.CR math.RA ·submitted 2026-09-12 01:47 UTC · v1
unusual

Abstract

The AES S-box is constructed from finite field inversion followed by a fixed affine transformation. Since inversion possesses intrinsic Frobenius symmetries among its coordinate realizations, we study how these basis symmetries are altered by outer affine transformations. We first develop a deterministic rigidity criterion for transformed inversion and apply it to the AES S-box. This shows that the linear part of the AES S-box affine transformation alone makes the transformed inversion map basis rigid. We then investigate the corresponding generic problem when the outer invertible linear transformation varies. The existence of a nontrivial linear stabilizer is reduced to a conjugacy problem for semilinear candidates arising from two sided linear equivalences of inversion, which we characterize in terms of relative norms and Frobenius orbits. We also determine the dimensions of the associated centralizer algebras exactly. These structural results imply that, for a uniformly chosen outer linear transformation, the probability that the linear stabilizer is nontrivial is bounded by $2^{-Ω(n^2)}$, with sharper finite dimensional bounds obtained from the exact conjugacy condition. Computational experiments independently verify the AES rigidity result, the conjugacy and centralizer formulas, and the finite dimensional estimates in small dimensions.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.CR ·2026-10-21 ·Zheng Zhang, Na Zhang
similarity 0.76
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 \(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.

0.11

Affine Symmetries of Polynomial Roots with Multiplicities and Applications to Constacyclic Codes

cs.IT math.NT ·2026-09-22 ·Li Zhu, Hongfeng Wu
similarity 0.55
Abstract

Let $f(X)$ be a polynomial over a finite field, and let its defining function record the multiplicities of its roots. In this paper, we introduce the affine stabilizer group and the affine stabilizer group scheme of the defining function of $f(X)$. These objects characterize the affine symmetries of the roots of $f(X)$ together with their multiplicities. We establish structural descriptions of these affine stabilizers and relate them to the coefficient structure of $f(X)$. In particular, the affine stabilizer group determines quotient structures of the defining function, which yield canonical descriptions of the corresponding semi-invariant polynomial spaces. The resulting coefficient constraints provide explicit restrictions on the possible supports of polynomials with prescribed affine symmetries. The affine stabilizer group scheme further captures infinitesimal symmetries arising from multiple roots and gives refined coefficient constraints beyond those obtained from ordinary affine transformations. We apply this framework to generator polynomials of constacyclic codes over finite fields. The affine stabilizer structure of a generator polynomial induces subcodes defined by semi-invariant conditions and provides constraints on their dimensions and Hamming distances. In the special case of multiplicative symmetries, the construction specializes to the support-primitive decomposition of constacyclic codes.

0.33

Linear Equivalence of Full Weight Spectrum Cyclic Orbit Codes

cs.IT cs.GT ·2026-11-03 ·Minjia Shi, Ferruh Ozbudak
theory similarity 0.53
Abstract · 12 pages

We determine the linear-equivalence classes within the two families of full weight spectrum one-orbit cyclic subspace codes. This solves the second open problem posed by Castello, Polverino and Zullo [J. Combin. Theory Ser. A 212 (2025) 106005]. For the first family, the criterion is a fractional linear transformation over $\F_q$ followed by a power of $q$-Frobenius. For the second family, it is an affine transformation over $\F_{q^2}$ together with a power of $q$-Frobenius. We use polynomial spaces over finite fields, the linear-isometry theorem for cyclic orbit codes, and trace duality. The arguments include parameters belonging to proper subfields of the ambient field.

0.13

The Mode of Null-A: Compositional Computation of a Generalized Inverse

cs.PL math.NA ·2026-09-29 ·Barak A. Pearlmutter, Jeffrey Mark Siskind
similarity 0.52
Abstract · Submitted to ICLR 2027

We present a novel algorithm for calculating the preimage of an affine space through a product ${J}={J}_{T-1}\cdots{J}_0$ of matrices ${J}_t$ of special form: finding the largest input space $\mathbf{X}$ such that $\mathbf{x}\in\mathbf{X}$ implies ${J}\mathbf{x}\in \mathbf{Y}$, where $\mathbf{Y}$ is a given output affine space. These special matrices arise in AD, where the Jacobians $J$ describing the linearized computation have precisely this structure: the product of a series of linearized primitive numeric operations. This allows us to use the new algorithm to formulate Null-A mode preimage AD, which finds the affine preimage through the Jacobian or Jacobian transpose of a numeric computation. This is a generalization of the inverse AD problem of solving ${J}\acute{\mathbf{x}}^{\ast}=\acute{\mathbf{y}}^{\ast}$ or ${J}^{T}\grave{\mathbf{y}}^{\ast}=\grave{\mathbf{x}}^{\ast}$. The key is to represent affine spaces in a fashion which lends itself to efficient preimage calculation, in a compositional and quasi-local fashion, through a succession of matrices ${J}_t$. Unlike previous methods, Null-A preimage mode AD allows the ${J}_t$ matrices to be non-square, corresponding to a computer program whose number of active variables swells and shrinks during the computation. When ${J}$ is square and the initial affine space is a single point, this finds the conventional inverse. But in the more general case, having the entire affine space provides freedom which can be leveraged in a problem-specific manner. We apply the method to small problems on-CPU where the $J_t$ are linearized scalar unary or binary numeric functions; and to larger problems on-GPU where the $J_t$ are linearized aggregate array operations like convolution and attention.

0.27

Concise tensors with maximal symmetries

cs.CC math.AGmath.GR ·2026-09-15 ·Annika Holtrup, Jeroen Zuiddam
theory similarity 0.51
Abstract

Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise $n\times n \times n$ tensors that are binding, and they determined the corresponding maximizing tensors to be the null algebra tensors. They left as an open problem to extend this to all concise $n \times n \times n$ tensors (i.e. dropping binding). We solve this problem: We prove that the largest stabilizer dimension of concise $n\times n\times n$ tensors is $n^2 + 1$ and the maximizers are the null algebra tensors (as in the binding case) and the skew symmetric tensor $e_1 \wedge e_2 \wedge e_3$. As part of our approach we obtain upper bounds on the stabilizer dimension of matrix tuples under left-right action (generalized Kronecker quiver representations), which we think are of independent interest.

0.27

On Lie-Algebraic Conditions for Finite-Dimensional Koopman Bilinear Embeddings of Control-Affine Systems

eess.SY math.OC ·2026-11-16 ·Natsuki Katayama, Yoshihiko Susuki
similarity 0.51
Abstract · 8 pages, 0 figure

Koopman bilinear representations for control-affine systems have attracted considerable attention. In this paper, we investigate, from a Lie-algebraic perspective, conditions under which a control-affine system admits a finite-dimensional Koopman bilinear embedding. Specifically, we focus on the Lie algebra generated by the drift and control vector fields. First, we show that the finite-dimensionality of the generated Lie algebra is a necessary condition for the existence of a Koopman bilinear embedding. Next, when the generated Lie algebra contains a nonzero nilpotent ideal, we derive a sufficient condition for the existence of such an embedding. Finally, through an example of a quadratic polynomial system, we demonstrate that the finite-dimensionality of the generated Lie algebra imposes strong restrictions on the vector fields, suggesting that exact finite-dimensional Koopman bilinear embeddings may be nongeneric.

0.31

The sum-of-squares complexity of linear-algebraic principles

cs.CC ·2026-11-03 ·Dmitriy Kunisky, Xifan Yu
similarity 0.50
Abstract · 41 pages

We study the degree needed for sum-of-squares (SoS) proofs of several basic principles of real linear algebra. For any $n\times n$ matrix $A$ of rank greater than $r$, the Weak Rank Principle states that the equations $XY^\top=A$ with $n\times r$ matrix variables $X, Y$ have no solution. We show that this principle requires degree exactly $2r+2$ to prove. On the other hand, for $A=I_n$, setting $X = Y$ gives the Tight Frame Principle, which has a degree-$4$ proof. For $n\times n$ matrices, proving that a right inverse is also a left inverse requires degree exactly $2n+2$, while proving that orthonormal rows imply orthonormal columns again has a degree-4 proof. Using our lower bounds, we also derive related SoS degree lower bounds for polynomial systems encoding sign rank, matrix rigidity, small-width homogeneous non-commutative algebraic branching programs, and tensor CP rank. Lastly, we show that quantitative bounds on the Frobenius norms of the factors in the Weak Rank Principle can lower the degree required to refute $XY^\top=I_n$, but sufficiently large bounds still preserve the exact degree $2r+2$ from the unbounded case, giving a quantitative version of the Archimedean property arising in classical results on SoS proofs.

0.28

A Weak Notion of Symmetry for Control Systems

eess.SY cs.RO ·2026-09-28 ·Jake Welde, Riley Link, Pieter van Goor
theory similarity 0.50
Abstract · 15 pages, 5 figures

Symmetry (or invariance) is a powerful structural property that enables efficient, effective solutions for estimation and control. However, the constraints imposed on a system's dynamics by classical invariance make symmetry a very rigid property, which may be broken by external forces or confined to only a portion of the overall system. Seeking greater flexibility, this work introduces a novel relaxed notion of symmetry, termed ``weak invariance'', in which the non-symmetric part of the dynamics (the ``residual'') can be captured entirely by another control system evolving on the symmetry group. Weakly invariant systems are strictly more general than classical invariant systems, but they nonetheless enjoy many similar favorable properties. In particular, we prove that any weakly invariant system admits a cascade decomposition in which the driven subsystem is group affine, showing that weak symmetry generalizes not only classical symmetry, but also the (thus far distinct) class of group affine systems. We also show that a weak symmetry with autonomous residual can be factored out of the system's error dynamics, enabling yet a greater reduction of dimensionality as compared to classical symmetries. Finally, we study the example of an aerial vehicle under the influence of gravity, for which we propose a nine-dimensional weak symmetry (strictly containing the system's familiar four-dimensional classical symmetry). Weak invariance thus generalizes classical symmetry while also preserving key structural properties, thereby laying a foundation for more flexible methods of symmetry-informed control.

0.28